乌龟棋

题解：动态规划

用dp[i][j][k][l]来表示第i+j* 2+k *3+l *4+1的格子可以取得的最大值
它可以由前i-1||(j-1) * 2||(k-1) * 3||(l-1) * 4的格子而来

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int a[maxn],cnt[maxn];
int dp[45][45][45][45];
void solve()
{
    int n,m,x;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        cnt[x]++;
    }
    dp[0][0][0][0]=a[1];
    for(int i=0;i<=cnt[1];i++)
    {
        for(int j=0;j<=cnt[2];j++)
        {
            for(int k=0;k<=cnt[3];k++)
            {
                for(int l=0;l<=cnt[4];l++)
                {
                    int ans=a[i+j*2+k*3+l*4+1];
                    if(i) dp[i][j][k][l]=max(dp[i-1][j][k][l]+ans,dp[i][j][k][l]);
                    if(j) dp[i][j][k][l]=max(dp[i][j-1][k][l]+ans,dp[i][j][k][l]);
                    if(k) dp[i][j][k][l]=max(dp[i][j][k-1][l]+ans,dp[i][j][k][l]);
                    if(l) dp[i][j][k][l]=max(dp[i][j][k][l-1]+ans,dp[i][j][k][l]);
                }
            }
        }
    }
    cout<<dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]<<endl;
}

int main()
{
    solve();
    return 0;
}