农夫过河:SuperOjP923
SB DP..
------------------------------------------------------------------------------------
国庆集训-DAY1总结
2015年10月09日 07:58
Set : SuperOj887
刚好大于的选发和刚好小于的选法数是一样的，因此只需用总的选法数减去分数一样的选法数再除以二
设f(i,j)表示前i堆石子，两个人的选的数xor起来为j的选法数（显然分数一样的选法数为f(n,0)）
[cqoi2013]二进制a+b
2015年8月08日 00:34
这道题蛮有意思的..
可以考虑DP，这样来设计状态：
f(ma,mb,mc,n,q)表示a用了ma个1，b用了mb个1，c用了mc个1，当前到第n位，q∈{0,1}表示是否有进位
然后只需枚举当前位a取0，b取0、a取1，b取1、a取1，b取0这三种情况，根据q来判断mc需要增加多少和答案需要增加多少
[Apio2010]特别行动队
2015年7月10日 21:20
这是道DP斜率优化的模板题啊...
首先很容易得出朴素的DP状态转移方程如下:
f(i) = max{f(j) + g(S(i) - S(j))} (0 < j < i)
其中，g(x) = a*x^2 + b*x + c , S(i) = Σ(k = 1,i)xk
展开、化简之后得:
f(i) = max(f(j) + a*S(j)^2 - b * S(j) - 2*a*S(i)*S(j)} + g(S(i))
[HNOI2008]玩具装箱toy
2015年7月09日 19:01
这道题貌似可以用斜率优化，不过不用也行，利用决策单调性同样可以设计出O(nlogn)的算法..
首先可以很容易得到朴素的状态转移方程:(f(x)表示只装前x个玩具的最优解)
f(x) = min{f(k) + cost(k + 1,x)}
其中,cost(i,j)为把[i,j]这个区间内的玩具装到一个箱子里的代价:cost(i,j) = (Sj - Si + j - i - T)^2
其中,Sx = Σ(i = 1,j)Ci，Ci即为第i个箱子的长度
我们可以很容易发现，对于j > i,若cost(k,j) > cost(k,i),那么一定有cost(k,j + 1) > cost(k,i)(原因是cost(k,x)的函数图像开口向上且只有一个极值),而对于j > i,也有若f(j) > f(i),那么f(j + 1) > f(i)(因为f(x)是由cost(i,j)定义的)
也就是说，若f(j)的最优决策是f(i),那么f(j + 1)的最优决策也是f(i)
