由于每种牌的分数是固定的,并且都会用到,
所以集合表示为每张牌用了多少次的情况的集合
闫氏dp分析法:
JAVA代码
import java.io.*;
import java.util.*;
public class Main{
static int N = 41;
static int[][][][] f = new int[N][N][N][N];
static int[] cnt = new int[5];
static int[] va = new int[360];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 1;i<=n;i++) va[i] = sc.nextInt();
for(int j = 1;j<=m;j++) cnt[sc.nextInt()]++;
//枚举当前用哪张卡
for(int a = 0;a<=cnt[1];a++)
for(int b = 0;b<=cnt[2];b++)
for(int c = 0;c<=cnt[3];c++)
for(int d = 0;d<=cnt[4];d++){
int ma = 0;
int path = 1+a+b*2+c*3+d*4;
if(a>0) ma = Math.max(ma,f[a-1][b][c][d]);
if(b>0) ma = Math.max(ma,f[a][b-1][c][d]);
if(c>0) ma = Math.max(ma,f[a][b][c-1][d]);
if(d>0) ma = Math.max(ma,f[a][b][c][d-1]);
f[a][b][c][d] = ma+va[path];
}
int res = f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];
System.out.println(res);
}
}