题目描述
线性DP
y总的题解: https://www.acwing.com/solution/content/3953/
样例
import java.util.*;
public class Main {
static final int N = 360, M = 41;
static int n;
static int m;
static int[] score = new int[N];
static int[][][][] f = new int[M][M][M][M];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
score[i] = sc.nextInt();
}
//存放每种卡片有多少张
int[] b = new int[5];
for (int i = 0; i < m; i++) {
int t = sc.nextInt();
b[t]++;
}
for (int A = 0; A <= b[1]; A++) {
for (int B = 0; B <= b[2]; B++) {
for (int C = 0; C <= b[3]; C++) {
for (int D = 0; D <= b[4]; D++) {
//走到当前格子所获得的积分
int t = score[A + B * 2 + C * 3 + D * 4];
//新状态的积分
int v = t;
if (A > 0) v = Math.max(v, f[A - 1][B][C][D] + t);
if (B > 0) v = Math.max(v, f[A][B - 1][C][D] + t);
if (C > 0) v = Math.max(v, f[A][B][C - 1][D] + t);
if (D > 0) v = Math.max(v, f[A][B][C][D - 1] + t);
//更新状态的积分
f[A][B][C][D] = v;
}
}
}
}
System.out.println(f[b[1]][b[2]][b[3]][b[4]]);
}
}