博客食用更佳
https://www.cnblogs.com/czyty114/p/14962876.html
A
$\;$
给定$n$个字符串$a_1,a_2,\cdots,a_n$和$b$，$q$次询问
每次询问给定$i_1,i_2,…,i_k$和$x,y$ $i_1<i_2<\cdots < i_k$
求出$a_{i_1}+a_{i_2}+\cdots+a_{i_k}和b[x…y]$的最长公共子序列
$n\leq 10, |b|\leq 10^3, q\leq 10^6$
20s,2048MB
观察到$q$很大，说明我们不大可能对于每组询问再在线的去处理
可能是预处理一些东西，然后对于每组询问快速的得到答案
Step 1
$\;$
不妨先去处理$v_{i,x,y}$表示$a_i$与$b[x..y]$的最长公共子序列
大概就是枚举一下$x$，然后在求一下$a_i$和$b[x\;to\;n]$就可以了
时间复杂度：$O(n \times |b|^2 \times |a|)$
上限是$10^9$，没有什么问题
$\;$
Step 2
$\;$
发现$n$很小，所以最多有1024种选法
设$f_{S,x,y}$表示选了$S$这个状态的字符串集，匹配$[x…y]$的最优答案
但你会发现一件事情，这样会导致空间达到$10^9$，不行。
考虑优化空间。
既然全部存不下来，我们不妨去一半一半的存，所谓的折半搜索
在查询的时候，我们就只需枚举一下断点取最大值就可以了
怎么求$f$?
在$x,S$和最后一个字符串固定的情况下，现在相当于我们是$y$一直向右移动，现在想要找到一个断点使得答案更优
若直接暴力枚举转移，时间复杂度必然会多出一个$|b|^3$，还要乘上一堆东西，不行。
Step 3 (决策单调性)
$\;$
考虑最优决策有什么性质，在$y$向右滑动的过程中，我们发现决策点也一定是单调不降的
设$ch_{i,j}$表示$[i…j]$的最优决策在哪里，即有：$ch_{i,j+1}\geq ch_{i,j}$
这个真的需要非常感性的理解
我口胡一波：若加上$j+1$后，对决策点有影响，我们肯定是$a_i$的某个位置和$j+1$，且这个位置应该在原先匹配的几对点的最后面
若刨去这个点，单看前面，那么决策点就一定不会往左挪，但有可能往后挪，使得让左边更宽敞，且右边因为腾出去了一个位置，可能就会导致最左边的那个点向右移
$\;$
然后就可以用决策单调性把$O(|b|^3)$优化成$O(|b|^2 log|b|)$
$\;$
Code
http://noi.ac/submission/131764
B
$\;$
现在有$n$个人，其中一些人可以进行搏斗，而搏斗关系构成了一张有向无环图，一条边$(u,v,w)$表示如果$v$打败了$u$，可以获得$w$的收益。
每个人有一个$a_i$，表示初始的经济是多少，且如果他这是第$x+1$次获胜，之前已获胜了$x$次，他会获得$n-x$的收益
设$X$为所有活下来的人的总收益，$Y$为一次都没赢过的人的数量，现在要最大化$\frac{X^k}{Y},(k\in \{1,2\})$
$n\leq 150,\;m\leq 500,\; a_i\leq 10000, \;w\leq 1000$
$\;$
我们注意到一个人能干掉很多个人，但不能被很多人干掉。
所以这就出现了一个类似二分图匹配的东西（但其实不是二分图匹配）
考虑用网络流来做
$\;$
Step 1 建图
$\;$
将每个点拆成两个点$x,x’$
因为一个人最多会被干掉一次，所以从源点$S$向$x$连一条容量为$1$，费用为$0$的边
考虑搏斗关系，显然会从$u$向$v’$连一条容量为$1$，费用为$w$
然后考虑一个点胜利之后的收益，所以从$x’$向汇点连容量为全为$1$，但费用是$n, n-1,n-2....$的边
然后我们直接跑一个最大费用流即可
$\;$
Step 2 处理Y
$\;$
我们发现这个$Y$非常的讨厌，比较难去维护它
有一种思路是：我们就去枚举$n-y$，即至少赢了一场的人的数量。
即：我们从$x’$向伪汇点$T’$连一条容量为1，费用为$INF+n$的边，然后从$x’$向汇点$T$连$n-1,n-2…$的边，然后从$T’$向$T$连一条容量为$y$的边
这样建有什么好处？
因为我们建了费用为正无穷的边，所以我们显然会贪心的把这些边给流满，也就说只要我们存在1种方案使得至少有$n-y$个人赢，我们的流一定会满足这种方案
而且在满足有$n-y$个人赢的情况下，因为跑的是最大流，我们显然会使其余的收益尽可能的大。
这样就满足了勒令$y$个人输，且求出在这种情况下最优收益是多少
Code
http://noi.ac/submission/131845
C
$\;$
给定一个$1,n$的排列，设其最长上升子序列长度为$m$
每一次询问给出$k$
选出$i_1,i_2,\cdots,i_m$，最大化$\sum_{j=2}^m ln(a_{i_j}-a_{i_{j-1}}+k)$
找特殊性质
$\;$
设$f_i$表示以$i$为结尾的最长上升子序列的长度
发现，所有$f_i=x$的点，随着下标增大，$a_i$是递减的。
由于$x$层在最终的dp中一定是由第$x-1$层转移而来的
一种朴素想法就是暴力枚举转移，复杂度$O(n^2)$
$\;$
又是决策单调性
为什么这玩意的转移还是满足决策单调性的呢?
假如说对于$f_i=f_j=x,(i<j)$,$i$的最优决策点是$k$，$j$的最优决策点$l$小于$k$
那么即可得到:$f_l+ln(a_j-a_l+k)\geq f_k+ln(a_j-a_k+k)$
但因为我们知道$f_l+ln(a_i-a_l+k)\leq f_k+ln(a_i-a_k+k)$
由于$ln$函数随着$x$增大增长的越来越慢，而两边$ln$里面相当于同时加上$a_j-a_i$
而又因为$a_l>a_k$，所以势必左边的增量会更少，那么出现矛盾了。
所以我们就可以用决策单调性解决这个问题
$\;$
