NOIP集训-10.13总结

农夫过河:SuperOjP923
SB DP..
 
------------------------------------------------------------------------------------
 

国庆集训DAY4总结

显而易见的DP
 

国庆集训-DAY1总结

Set : SuperOj887
刚好大于的选发和刚好小于的选法数是一样的,因此只需用总的选法数减去分数一样的选法数再除以二
设f(i,j)表示前i堆石子,两个人的选的数xor起来为j的选法数(显然分数一样的选法数为f(n,0))
 

[cqoi2013]二进制a+b

这道题蛮有意思的..
可以考虑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]特别行动队

 
这是道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

BZOJ1010...

这道题貌似可以用斜率优化,不过不用也行,利用决策单调性同样可以设计出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)