【1】BZOJ1713
F[i][j]=max{F[i1][j1] - (sA[i-1]-sA[i1])2 - (sB[j-1]-sB[j1])2} + A[i]*B[j], 0<=i1<i, 0<=j1<j
对这个式子进行化简:
F[i][j]=max{F[i1][j1] - sA[i1]2 + 2*sA[i-1]*sA[i1] - sB[j1]2 + 2*sB[j-1]*sB[j1]}+A[i]*B[j]-sA[i-1]2-sB[j-1]2
对于一维的情况,很容易处理——中间就是一条直线,然而这是二维的,对于这种2D/2D的DP方程,要优化到O(N2)级别,需要两步。
注意到决策式中除了F[i1][j1]外,其它部分都要么只与i1有关,要么只与j1有关。因此,可以把阶段i的各个状态作为一个整体,在之前得出的各个F[i][j]中,对于相同的j,找到对于目前的i,最优的那个决策——注意,对于相同的j1,里面所有与j1有关的东西都可以先不考虑了,只考虑(F[i1][j1] - sA[i1]2 + 2*sA[i-1]*sA[i1])对于目前i的最优决策。这一步可以在这些直线形成的上凸壳中找到,且满足决策单调性,可以用一个栈处理(斜率优化)。然后,将这些最优决策以j为自变量再组成一些直线,用栈维护它们的上凸壳,对于每个j,找到最优值即可。
注意事项:在栈中删除直线的时候,如果之前的最优决策是这个被删掉的直线,则要将最优决策先置为不存在,然后再插入新直线后设为新直线。另外,要特别注意平行的情况。

【2】LCIS
经典问题,利用上面的分步优化思想,很容易用线段树得到一个O(N2logN)的做法。

【3】[SCOI2010]股票交易
F[i][j]=max{F[i-1][j], max{F[i-W-1][j-a]-A*a, F[i-W-1][j+b]+b*B}}, j<=maxP, 1<=a<=maxA, 1<=b<=maxB
注意对于相同的j,计算方法是一样的,且是一条直线(由于有范围所以其实是线段)。
所以,计算阶段i时,可以将(i-W-1)阶段所有的决策当成线段插入,这些线段的斜率都相等,因此比较好维护,只需要判断边界即可。

注意,NOI2011的show虽然也符合对于相同的j计算方法一样,但它就不能优化,因为它的决策是不连续且无规律的,没有任何几何性质。因此,它只能用O(N3)的算法计算出所有状态。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理