乌龟棋（记忆化dfs）

题意：

有一堆卡片，卡片上有1-4其中一个数，数字决定向前走的步数，走到某处就获得该点对应的分数，如何调整使用卡片顺序使得到达终点 n 时的得分最大。

分析：

动态规划每一步促使结果最优解，很明显思路是 dp 或者记忆化搜索（感觉搜索比较好写）
dfs(int k,int a1,int a2,int a3,int a4)

k表示当前位置，a1表示数字1卡片使用次数，a2表示数字2卡片使用次数，a3表示数字3卡片使用次数，a4表示数字4卡片使用次数，

由此有四个搜索方向：（前提是有卡片剩余）
使用1卡片：dfs(k+1,a1+1,a2,a3,a4)
使用2卡片：dfs(k+2,a1,a2+1,a3,a4)
使用3卡片：dfs(k+3,a1,a2,a3+1,a4)
使用4卡片：dfs(k+4,a1,a2,a3,a4+1)

最后 if（k == n） 统计答案就行了
然后很自然地 TLE 了，O（4^120）还是太大了，要记忆化处理一下。
用dp[a1][a2][a3][a4] 记录每次局部最优答案即可。

代码：

#include <bits/stdc++.h>
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
int mod=1e9+7;
int a[400],b[150],c[5],dp[120][120][120][120];
void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
int n,m,i,j;
int dfs(int k,int a1,int a2,int a3,int a4){
    if(k == n) return a[k];
    if(dp[a1][a2][a3][a4]) return dp[a1][a2][a3][a4];
    int cnt = 0;
    if(a1 < c[1]){
        cnt = max(cnt,dfs(k+1,a1+1,a2,a3,a4));
    }
    if(a2 < c[2]){
        cnt = max(cnt,dfs(k+2,a1,a2+1,a3,a4));
    }
    if(a3 < c[3]){
        cnt = max(cnt,dfs(k+3,a1,a2,a3+1,a4));
    }
    if(a4 < c[4]){
        cnt = max(cnt,dfs(k+4,a1,a2,a3,a4+1));
    }
    return dp[a1][a2][a3][a4] = cnt + a[k];
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    for(i=1;i<=m;i++){
        cin>>b[i];
        c[b[i]]++;
    }
    cout<<dfs(1,0,0,0,0)<<endl;
}