既然我放在动态规划这个分类，不是动态规划是什么？？？
既然没有规定乌龟卡的使用顺序，那么用桶排，sum[i]记录i类卡的张数。
状态设计：当数据范围不大，并且情况不多的题，可以试试每一维记录一个元素的状态。dp[a][b][c][d]代表用了a张1类牌，b张2类牌，c张3类牌和d张4类牌时可以获得的最大价值。
边界条件：当dp[0][0][0][0]时，没有用牌，那么站在原地1处，获得的价值是v[1]。
转移方程：4重循环分别枚举a，b，c，d从0到sum[]，四种类型的乌龟牌分别用了几张，step计算了这次如果转移可以获得多少价值，下面用分支结构一一讨论：
（1）如果a不为0 dp[a][b][c][d]=max(dp[a][b][c][d],dp[a-1][b][c][d]+step);
（2）如果b不为0 dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b-1][c][d]+step);
（3）如果c不为0 dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c-1][d]+step);
（4）如果d不为0 dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c][d-1]+step);
这样做的原因是数组的下标为非负数，答案自然是dp[sum[1]][sum[2]][sum[3]][sum[4]]。
#include<bits/stdc++.h> using namespace std; const int N=355,M=10,T=125; int n,m,v[N],sum[M],dp[T][T][T][T]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&v[i]); memset(sum,0,sizeof(sum)); for(int i=1;i<=m;i++) { int x; scanf("%d",&x); sum[x]++; } dp[0][0][0][0]=v[1]; for(int a=0;a<=sum[1];a++) for(int b=0;b<=sum[2];b++) for(int c=0;c<=sum[3];c++) for(int d=0;d<=sum[4];d++) { int step=a*1+b*2+c*3+d*4+1; step=v[step]; if(a!=0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a-1][b][c][d]+step); if(b!=0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b-1][c][d]+step); if(c!=0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c-1][d]+step); if(d!=0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c][d-1]+step); } printf("%d\n",dp[sum[1]][sum[2]][sum[3]][sum[4]]); return 0; }
原文：https://www.cnblogs.com/Siv0106/p/11721926.html