【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。

本文链接:http://kaispace.com.cn/index.php/archives/551/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者