动态规划，设 f [ i ][ j ][ k ][ l ] 表示1、2 、3、4号牌用了多少张后，所能够获得的分数的最大值。
因为棋子从1开始走，棋子走过的路程就等于已用的牌张数×牌上的点数 ：
pass= i×1 + j×2 + k×3 + l×4
所以只要枚举每种牌用过的次数，动态转移就行了。
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<queue> #include<vector> #include<deque> #include<stack> #include<map> #include<set> using namespace std; #define maxn 351 int a[maxn]; int f[41][41][41][41]; int t[10]; int n,m; inline int read() { int kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(ls==‘-‘) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return kr*xs; } int main() { memset(t,0,sizeof(t)); n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); int lck; for(int i=1;i<=m;i++) { lck=read(); t[lck]++; } f[0][0][0][0]=a[1];//刚开始在 1 位置 for(int i=0;i<=t[1];i++) { for(int j=0;j<=t[2];j++) { for(int k=0;k<=t[3];k++) { for(int l=0;l<=t[4];l++) { int pass=i+j*2+k*3+l*4+1;//所到达的位置，注意“+1” if((!i)&&(!j)&&(!k)&&(!l)) continue;//一张牌都没用就跳过 if(i) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[pass]); if(j) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[pass]); if(k) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[pass]); if(l) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[pass]);//暴力转移 } } } } printf("%d\n",f[t[1]][t[2]][t[3]][t[4]]);//输出 return 0; }
原文：https://www.cnblogs.com/lck-lck/p/9688561.html