明星网页网站制作,网站开发工作流审批流,线下推广渠道,手机选择网站312. 乌龟棋 - AcWing题库
思路#xff1a; 原来没有碰到过类似的题#xff1a; dp数组为思维#xff1a;dp[i][j][k][r]#xff0c;分别表示用了i个第一类型卡片#xff0c;j个第二类型卡片...所到的格子数的最大分数#xff0c;为啥不用记录乌龟到了哪里呢#xff1…
312. 乌龟棋 - AcWing题库
思路 原来没有碰到过类似的题 dp数组为思维dp[i][j][k][r]分别表示用了i个第一类型卡片j个第二类型卡片...所到的格子数的最大分数为啥不用记录乌龟到了哪里呢因为i*1j*2k*3r*4已经表明了小乌龟的终点位置了。状态转移方程式dp[i][j][k][r]max(dp[i-1][j][k][r],dp[i][j-1][k][r],...)a[i*1j*2k*3r*4]数组初始化dp[0][1][2][3]0 C代码
#includebits/stdc.h
using namespace std;int g[41][41][41][41];
int n,m;
int a[400];
int b[5];int main(){cinnm;for(int i0;in;i){cina[i];}for(int i0;im;i){int temp;cintemp;b[temp];}g[0][0][0][0]a[0];for(int i0;ib[1];i){for(int j0;jb[2];j){for(int k0;kb[3];k){for(int r0;rb[4];r){if(i-10){g[i][j][k][r]max(g[i][j][k][r],g[i-1][j][k][r]a[i2*j3*k4*r]);}if(j-10){g[i][j][k][r]max(g[i][j][k][r],g[i][j-1][k][r]a[i2*j3*k4*r]);}if(k-10){g[i][j][k][r]max(g[i][j][k][r],g[i][j][k-1][r]a[i2*j3*k4*r]);}if(r-10){g[i][j][k][r]max(g[i][j][k][r],g[i][j][k][r-1]a[i2*j3*k4*r]);}}}}}coutg[b[1]][b[2]][b[3]][b[4]];return 0;
} python代码
n,mmap(int,input().split())
alist(map(int,input().split()))
b_templist(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-10:g[i][j][k][r]max(g[i][j][k][r],g[i-1][j][k][r]a[ij*2k*3r*4]);if j-10:g[i][j][k][r]max(g[i][j][k][r],g[i][j-1][k][r]a[ij*2k*3r*4]);if k-10:g[i][j][k][r]max(g[i][j][k][r],g[i][j][k-1][r]a[ij*2k*3r*4]);if r-10:g[i][j][k][r]max(g[i][j][k][r],g[i][j][k][r-1]a[ij*2k*3r*4]);
print(g[b[1]][b[2]][b[3]][b[4]])
