题目的核心在于最后一句,我们会刚好把所有卡片用完。
因此这道题不是对我们的棋盘索引的dp,而是对卡片数量的dp。假设我们总共有 a 张 1步卡,b张2步卡,c张3步卡,d张四步卡
最终状态一定是dp[a][b][c][d],因为我们最后会把卡片全用完
那么对于其中任意状态dp[i][j][k][l]到底是怎么转移的呢?
dp[i][j][k][l]表示当前状态用了i 张 1步卡,j张2步卡,k张3步卡,l张四步卡.所以当前所在棋盘的索引位置为cur=1i+2j+3k+4l;
如果我们的 i 大于0,我们可能是从一步前转移过来的,即上一步是dp[i-1][j][k][l]
同理如果我们的j大于0,我们则可能是从两步前转移过来的,即上一步是dp[i][j-1][k][l]
以此类推就得出我们下面的代码。
java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int[] g = new int[n];
int[] cnt = new int[5];
int[][][][] dp = new int[41][41][41][41];
for(int i = 0 ; i < n ; i++){
g[i] = input.nextInt();
}
for(int i = 1 ; i <= m ; i++){
cnt[input.nextInt()]++;
}
dp[0][0][0][0] = g[0];
for(int i = 0 ; i <= cnt[1] ; i++){
for(int j = 0 ; j <= cnt[2] ; j++){
for(int k = 0 ; k <= cnt[3] ; k++){
for(int l = 0 ; l <= cnt[4] ; l++){
int cur = i * 1 + j * 2 + k * 3 + l * 4;//当前棋盘位置索引
if(i != 0) dp[i][j][k][l] = Math.max(dp[i][j][k][l] , dp[i-1][j][k][l]+g[cur]);
if(j != 0) dp[i][j][k][l] = Math.max(dp[i][j][k][l] , dp[i][j-1][k][l]+g[cur]);
if(k != 0) dp[i][j][k][l] = Math.max(dp[i][j][k][l] , dp[i][j][k-1][l]+g[cur]);
if(l != 0) dp[i][j][k][l] = Math.max(dp[i][j][k][l] , dp[i][j][k][l-1]+g[cur]);
}
}
}
}
System.out.println(dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
}
}
哥们你是个天才