题目传送门
luogu
分析
暴力的来看 这道题用动态规划求解，则可以定义状态 $ f[i][j][k][l] $ ，表示使用了 $ i $ 张 $ a $ 卡片, $ j $ 张 $ b $ 卡片, $ k $ 张 $ c $ 卡片, $ l $ 张 $ d $ 卡片后可以获得的最大分数，可以将它理解为一个多维的走楼梯问题，每次有 $ 4 $ 种走法
状态转移方程如下
1
2
3
4
5
| if(i != 0) dp[i][j][l][k] = max(dp[i][j][l][k], dp[i - 1][j][l][k] + s[t]);
if(j != 0) dp[i][j][l][k] = max(dp[i][j][l][k], dp[i][j - 1][l][k] + s[t]);
if(l != 0) dp[i][j][l][k] = max(dp[i][j][l][k], dp[i][j][l - 1][k] + s[t]);
if(k != 0) dp[i][j][l][k] = max(dp[i][j][l][k], dp[i][j][l][k - 1] + s[t]);
|
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 355;
int n, m, card[10], a[MAXN], f[45][45][45][45];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
int temp;
for(int i = 1; i <= m; i ++) {
scanf("%d", &temp);
card[temp] ++;
}
f[0][0][0][0] = a[1];
for(int i = 0; i <= card[1]; i ++) {
for(int j = 0; j <= card[2]; j ++) {
for(int k = 0; k <= card[3]; k ++) {
for(int l = 0; l <= card[4]; l ++) {
int t = 1 + i + j * 2 + k * 3 + l * 4;
if(i > 0) f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[t]);
if(j > 0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[t]);
if(k > 0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[t]);
if(l > 0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[t]);
}
}
}
}
printf ("%d", f[card[1]][card[2]][card[3]][card[4]]);
return 0;
}
|