动态规划

一道很正的动态规划题，直接进行分析：
原问题：选取所有卡片到最后一个格子是能够得到的最大分数；
子问题：四种卡片分别选i,j,k,l张时能得到的最大分数；
记dp[i][j][k][l]为四种卡片分别选出了i,j,k,l张时能够取得的最大分数。

有的人可能会按“前i个格子如何选取卡片”类似这样的套路分析，这里要注意的是，当每种卡片的个数确定了以后，走到的格子也是确定的，同时题目还确保了使用所有的卡片可以恰好到达最后一个格子，这就更没有必要讨论“前几个格子了”。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e6+9;
const ll maxx=1e12+9;

int n,m,a[555],b[5];
int dp[55][55][55][55];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++)
    {
        int num;
        scanf("%d",&num);
        b[num]++;
    }
    dp[0][0][0][0]=a[0];
    for(int i=0;i<=b[1];i++)
        for(int j=0;j<=b[2];j++)
            for(int k=0;k<=b[3];k++)
                for(int l=0;l<=b[4];l++)
                {
                    if(i) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+a[i+2*j+3*k+4*l]);
                    if(j) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+a[i+2*j+3*k+4*l]);
                    if(k) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+a[i+2*j+3*k+4*l]);
                    if(l) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+a[i+2*j+3*k+4*l]);
                }
    printf("%d\n",dp[b[1]][b[2]][b[3]][b[4]]);
}