【dp】乌龟棋
乌龟棋
解题思路
大佬们可能会疑惑为什么我放一道这么简单的 dp 在这里。
首先是因为我 dp 特别弱,普及 dp 都做不出。。。第二是因为这道题有一个特点:数据范围很小。
写这篇博客最大的知识点就是懂得看数据范围。
我最开始做的时候以为是一道一维 dp,然后没过脑子就写了一个类似背包的东西就挂了。最开始并没有在意数据范围,查不出错,于是去看了几篇题解。发现大佬们都是用四维数组做的。
这道题中 $dp[i][j][k][l]$ 代表用了 i 个 1,j 个 2,c 个 3,d 个 4 后的最大答案。
于是状态转移方程就特别好推了:
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+point[4*l+3*k+2*j+i+1]);
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+point[4*l+3*k+2*j+i+1]);
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+point[4*l+3*k+2*j+i+1]);
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+point[4*l+3*k+2*j+i+1]);
当然到这里还没结束,你会发现有 i -1,j- 1 这种不和谐的东西在这里,于是需要特判:
if(i!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+point[4*l+3*k+2*j+i+1]);
if(j!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+point[4*l+3*k+2*j+i+1]);
if(k!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+point[4*l+3*k+2*j+i+1]);
if(l!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+point[4*l+3*k+2*j+i+1]);
在这个特判又卡了好久。。。
数据范围
如果在 20 以内可能是状压 DP,3000 以内可能是二维,500 以内可能是三维,50 以内可能是四维。
以及要注意开 long long。