从题解里看到的话，挂出来警醒自己：DP 有三要素：先确定阶段，再确定状态，最后根据决策写出方程。
暴力四维dp枚举从每一种卡牌转移过来的答案，最后答案就是dp每一个卡牌的数量。
code
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
| #include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn = 350;
inline int read(){
char ch; int f = 1,res = 0; ch = getchar();
while (!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) {res = res * 10 + (ch - '0'); ch = getchar();}
return res * f;
}
int n,m;
int c[maxn],a[maxn],cnt[maxn];
int dp[50][50][50][50];
signed main(){
n = read(); m = read();
for (int i = 1;i <= n;i++) a[i] = read();
for (int i = 1;i <= m;i++) c[i] = read(),cnt[c[i]]++;
dp[0][0][0][0] = a[1];
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 s = 0;s <= cnt[4];s++){
int pos = 1 + 1 * i + 2 * j + 3 * k + 4 * s;
if (i != 0) dp[i][j][k][s] = max(dp[i][j][k][s],dp[i - 1][j][k][s] + a[pos]);
if (j != 0) dp[i][j][k][s] = max(dp[i][j][k][s],dp[i][j - 1][k][s] + a[pos]);
if (k != 0) dp[i][j][k][s] = max(dp[i][j][k][s],dp[i][j][k - 1][s] + a[pos]);
if (s != 0) dp[i][j][k][s] = max(dp[i][j][k][s],dp[i][j][k][s - 1] + a[pos]);
}
}
}
}
cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]];
return 0;
}
|
很简单的线性dp入门题，虽然是技术但是要求方案有序，式子也很简单。
tips：注意看，这个男人在写dp的时候试图从dp[i][]转移
code