AcWing---乌龟棋---线性dp

312. 乌龟棋 - AcWing题库 

思路：

原来没有碰到过类似的题：

1. dp数组为思维：dp[i][j][k][r]，分别表示用了i个第一类型卡片，j个第二类型卡片...所到的格子数的最大分数，为啥不用记录乌龟到了哪里呢？因为i*1+j*2+k*3+r*4已经表明了小乌龟的终点位置了。
2. 状态转移方程式dp[i][j][k][r]=max(dp[i-1][j][k][r],dp[i][j-1][k][r],...)+a[i*1+j*2+k*3+r*4]
3. 数组初始化：dp[0][1][2][3]=0

C++代码：

#include<bits/stdc++.h>
using namespace std;int g[41][41][41][41];
int n,m;
int a[400];
int b[5];int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<m;i++){int temp;cin>>temp;b[temp]++;}g[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 r=0;r<=b[4];r++){if(i-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i-1][j][k][r]+a[i+2*j+3*k+4*r]);}if(j-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i][j-1][k][r]+a[i+2*j+3*k+4*r]);}if(k-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k-1][r]+a[i+2*j+3*k+4*r]);}if(r-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k][r-1]+a[i+2*j+3*k+4*r]);}}}}}cout<<g[b[1]][b[2]][b[3]][b[4]];return 0;
}

 python代码：

n,m=map(int,input().split())
a=list(map(int,input().split()))
b_temp=list(map(int,input().split()))
b=[0]*5
for i in b_temp:b[i]+=1g=[[[[0 for _ in range(41)] for _ in range(41)] for _ in range(41)] for _ in range(41)]
g[0][0][0][0]=a[0]
for i in range(b[1]+1):for j in range(b[2]+1):for k in range(b[3]+1):for r in range(b[4]+1):if i-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i-1][j][k][r]+a[i+j*2+k*3+r*4]);if j-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i][j-1][k][r]+a[i+j*2+k*3+r*4]);if k-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k-1][r]+a[i+j*2+k*3+r*4]);if r-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k][r-1]+a[i+j*2+k*3+r*4]);
print(g[b[1]][b[2]][b[3]][b[4]])