乌龟棋

题意：
有一个长度为n的一维数组，每个元素有一个分值，你一开始在第一个元素的位置（1），你有m张卡片，有1，2，3，4四种类型，使用卡片可以让你移动等价于卡片数值的格数，然后将移动后到达位置的分值加上，求最大分值为多少？（使用完所以卡片后一定到位置n）

思路：
像这种类型的题九成用dp，做dp题你需要考虑一个状态是怎么来的。
dp[i][j][o][l][r]表示在第i个位置有j张1，o张2，l张3，r张4的最大分数为多少。
它可以是第i-1个位置使用一张1来。
它可以是第i-2个位置使用一张2来。
它可以是第i-3个位置使用一张3来。
它可以是第i-4个位置使用一张4来。
由于直接数值有点大，会爆内存，而一个位置的值只与前四个位置有关，所以用滚动数组减少内存的使用。

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int inf=1000000007;

int dp[5][41][41][41][41];
int a[355], p[5];

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0; i<m; i++)
    {
        int x;
        scanf("%d",&x);
        p[x]++;
    }
    memset(dp,-1,sizeof(dp));
    dp[1][p[1]][p[2]][p[3]][p[4]]=a[1];
    for(int i=2; i<=n; i++)
    {
        for(int j=0; j<=p[1]; j++)
        {
            for(int o=0; o<=p[2]; o++)
            {
                for(int l=0; l<=p[3]; l++)
                {
                    for(int r=0; r<=p[4]; r++)
                    {
                        dp[i%5][j][o][l][r]=-1;
                        if(i>=2&&dp[(i%5-1+5)%5][j+1][o][l][r]!=-1)
                            dp[i%5][j][o][l][r]=max(dp[i%5][j][o][l][r],dp[(i%5-1+5)%5][j+1][o][l][r]+a[i]);
                        if(i>=3&&dp[(i%5-2+5)%5][j][o+1][l][r]!=-1)
                            dp[i%5][j][o][l][r]=max(dp[i%5][j][o][l][r],dp[(i%5-2+5)%5][j][o+1][l][r]+a[i]);
                        if(i>=4&&dp[(i%5-3+5)%5][j][o][l+1][r]!=-1)
                            dp[i%5][j][o][l][r]=max(dp[i%5][j][o][l][r],dp[(i%5-3+5)%5][j][o][l+1][r]+a[i]);
                        if(i>=5&&dp[(i%5-4+5)%5][j][o][l][r+1]!=-1)
                            dp[i%5][j][o][l][r]=max(dp[i%5][j][o][l][r],dp[(i%5-4+5)%5][j][o][l][r+1]+a[i]);
                    }
                }
            }
        }
    }
    printf("%d\n",dp[n%5][0][0][0][0]);
    return 0;
}