小明過生日的時候，爸爸送給他一副烏龜棋當作禮物。 烏龜棋的棋盤是一行 N個格子，每個格子上一個分數（非負整數） 。棋盤第 1 格是唯一的起點，第 N格是終點，游戲要求玩家控制一個烏龜棋子從起點出發走到終點。 烏龜棋中 M 張爬行卡片，分成 4 種不同的類型（M 張卡片中不一定包含所有 4 種類型的卡片，見樣例） ，每種類型的卡片上分別標有 1、2、3、4 四個數字之一，表示使用這種卡片後，烏龜棋子將向前爬行相應的格子數。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片， 控制烏龜棋子前進相應的格子數， 每張卡片只能使用一次。游戲中，烏龜棋子自動獲得起點格子的分數，並且在後續的爬行中每到達一個格子，就得到該格子相應的分數。 玩家最終游戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的分數總和。 很明顯，用不同的爬行卡片使用順序會使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多。 現在，告訴你棋盤上每個格子的分數和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？ Input 第 1 行2 個正整數 N和 M，分別表示棋盤格子數和爬行卡片數。 第 2 行 N個非負整數，a1, a2, ……, aN，其中 ai 表示棋盤第 i 個格子上的分數。 第 3 行M 個整數，b1,b2, ……, bM，表示 M 張爬行卡片上的數字。 輸入數據保證到達終點時剛好用光 M 張爬行卡片，即 N−1=∑b_i (1≤i≤m) Output 輸出只有 1行，1 個整數，表示小明最多能得到的分數。 1 ≤ N≤ 350，1 ≤M≤ 120，且 4 種爬行卡片，每種卡片的張數不會超過 40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤M。輸入數據保證 N−1=∑b_i (1≤i≤m) Sample Input 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 Sample Output 73 Hint 小明使用爬行卡片順序為 1，1，3，1，2，得到的分數為 6+10+14+8+18+17=73。注意，由於起點是 1，所以自動獲得第 1 格的分數 6。 提交地址： https://vijos.org/p/1775 下面代碼來之 jiangzh7 思路 ： 顯然這是一道動規的題目，狀態設計可以用四維f[a][b][c][d]來維護，表示f["1"的張數]["2"的張數]["3"的張數]["4"的張數] 方程就很顯然了 f[a][b][c][d]=max{(a>0) f[a-1][b][c][d]+a[a*1+b*2+c*3+d*4], (b>0) f[a][b-1][c][d]+a[a*1+b*2+c*3+d*4], (c>0) f[a][b][c-1][d]+a[a*1+b*2+c*3+d*4], (d>0) f[a][b][c][d-1]+a[a*1+b*2+c*3+d*4]} 當然，由於第一個點自動得分，所以f[0][0][0][0]=a[1]（這也是為什麼我們只用計算每一部終點的得分，可以確保起點已經計算） [cpp] /* C++ Code http://blog.csdn.net/jiangzh7 */ #include<cstdio> #define MAXN 400 int n,m,a[MAXN],sum[5]; int f[50][50][50][50]; int main() { freopen("tortoise.in","r",stdin); freopen("tortoise.out","w",stdout); scanf("%d%d",&n,&m); int i,j,k,t,x; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=m;i++) {scanf("%d",&x);sum[x]++;} f[0][0][0][0]=a[1]; for(i=0;i<=sum[1];i++) for(j=0;j<=sum[2];j++) for(k=0;k<=sum[3];k++) for(t=0;t<=sum[4];t++) { if(i>=1)f[i][j][k][t]>?=f[i-1][j][k][t]+a[1+i*1+j*2+k*3+t*4]; if(j>=1)f[i][j][k][t]>?=f[i][j-1][k][t]+a[1+i*1+j*2+k*3+t*4]; if(k>=1)f[i][j][k][t]>?=f[i][j][k-1][t]+a[1+i*1+j*2+k*3+t*4]; if(t>=1)f[i][j][k][t]>?=f[i][j][k][t-1]+a[1+i*1+j*2+k*3+t*4]; } printf("%d",f[sum[1]][sum[2]][sum[3]][sum[4]]); return 0; } 也可以用 下面的方法 [cpp] #include<stdio.h> #include<string.h> int step[400],cn[5],f[50][50][50][50]; int mmax(int a,int b,int c,int d) { int mx=0; if(mx<a) mx=a; if(mx<b) mx=b; if(mx<c) mx=c; if(mx<d) mx=d; return mx; } int DFS(int x) { int a1=0; int a2=0; int a3=0; int a4=0; if(x==1) return step[1]; if(x<=0) return 0; if(f[cn[1]][cn[2]][cn[3]][cn[4]]) return f[cn[1]][cn[2]][cn[3]][cn[4]]; if(cn[1]!=0) {cn[1]--;a1=DFS(x-1)+step[x]; cn[1]++;} if(cn[2]!=0) {cn[2]--;a2=DFS(x-2)+step[x]; cn[2]++;} if(cn[3]!=0) {cn[3]--;a3=DFS(x-3)+step[x]; cn[3]++;} if(cn[4]!=0) {cn[4]--;a4=DFS(x-4)+step[x]; cn[4]++;} f[cn[1]][cn[2]][cn[3]][cn[4]]=mmax(a1,a2,a3,a4); return f[cn[1]][cn[2]][cn[3]][cn[4]]; } int main() { int n,m,num,i; while(scanf("%d %d",&n,&m)!=EOF) { memset(f,0,sizeof(f)); memset(cn,0,sizeof(cn)); for(i=1;i<=n;i++) scanf("%d",&step[i]); for(i=1;i<=m;i++) { scanf("%d",&num); cn[num]++; } int ans; ans=DFS(n); printf("%d\n",ans); } return 0; }
