NOIP2010乌龟棋讲解

显示全部楼层 · 2011-3-11 13:22:28

四维？我记得我三维过的f[j,k,l] 表示使用 j 张走一步，k 张走两步，l 张走三步的最大分数其实 for 要写四个第一个 i 可以在数组中省去，因为 f 是 f[i-1] 推出来的然后走四步就是 i - j - k - l ，但要判一下是否大于等于0...

千问 · 2011-3-11 13:22:28

我也是四维的。DP[i,j,k,l]表示走到了i，4的牌用的j张，3的k张，2的l张，1的就是（i-j*4-k*3-l*2）dp方程我就我不写了...

千问 · 2011-3-11 13:22:28

该题显然法可证用动规作，数据也不大，动规从理论上来讲完全可行。由于只能从左向右走，就很容易的出以下方程：F[t1,t2,t3,t4]=max{F[t1-1,t2,t3,t4]，F[t1,t2-1,t3,t4]，F[t1,t2,t3-1,t4]，F[t1,t2,t3,t4-1]}+a[t1+t2*2+t3*3+t4*4]（ti是的第i种牌的张数，F...

千问 · 2011-3-11 13:22:28

四维背包，dp[i,j,k,l]分别表示当前四种卡片已经使用i,j,k,l张时你所能得到的最大分数，边界条件dp[i,j,k,l]=0 当然，你如果怕爆内存，可以变成三维数组dp[i,j,k]，以为l=n-i-j-k是可以推算出来的，没有占内存的必要。这个三维背包是最简单的满分算法了！...