乌龟棋

解题思路

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