题目:https://www.luogu.org/problem/show?pid=1541
题意:
每个格子有一个值，可以有限定次数地走1,2,3,4步，求经过的格子的值总和
做法：
一开始想到的自然是n*k1*k2*k3*k4的DP，五维数组，内存可以滚动，但是时间复杂度...
后来发现其实可以直接忽略步数，直接开四维
dp[i][j][k][l]：分别用了几张卡片取得的值
[code lang="cpp"]
#include<cstdio>
#include<cstring>
#define MAXC 41
#define MAXN 351
using namespace std;
int n, m;
int dp[MAXC][MAXC][MAXC][MAXC];
int card[4];
int a[MAXN];

int max(int a, int b){
return a > b? a: b;
}

int main(){
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
memset(card, 0, sizeof(card));
scanf("%d%d", &n, &m);

for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++){
int t;
scanf("%d", &t);
card[--t]++;
}
for (int i = 0; i <= card[0]; i++)
for (int j = 0; j <= card[1]; j++)
for (int k = 0; k <= card[2]; k++)
for (int l = 0; l <= card[3]; l++)
for (int p = 0; p <= 3; p++){
if(p == 0 && i > 0) dp[i][j][k][l] = max(dp[i - 1][j][k][l] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
else if(p == 1 && j > 0) dp[i][j][k][l] = max(dp[i][j - 1][k][l] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
else if(p == 2 && k > 0) dp[i][j][k][l] = max(dp[i][j][k - 1][l] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
else if(p == 3 && l > 0) dp[i][j][k][l] = max(dp[i][j][k][l - 1] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
}
printf("%d", dp[card[0]][card[1]][card[2]][card[3]] + a[0]);
}
[/code]