乌龟棋

解题思路

大佬们可能会疑惑为什么我放一道这么简单的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/

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