题目大意
有四种卡片,它们分别可以让你前进1格,2格,3格和4格.在前进的道路上到达每个格子都会得到对应的积分.现在分别给出四种卡片的数量,求用完所有卡片能获得的最大积分和
思路
由于卡片只有4种,且每种的数量不超过20张,所以想到开四维dp,用dp[i][j][k][z]来表示用掉i张卡片4,j张卡片3,k张卡片2,z张卡片1时能获得的最大积分和.状态转移方程为:
dp[i][j][k][z] = max(dp[i][j][k][z],dp[i - 1][j][k][z]+a[t]);
dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j-1][k][z]+a[t]);
dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k-1][z]+a[t]);
dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k][z - 1] + a[t]);
代码如下:
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define N 356
int dp[41][41][41][41];
int a[N],b[5];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m,x; cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= m; i++) {
cin >> x;
//分别统计四种卡片的数目
b[x]++;
}
int t;
//在第一格的分数
dp[0][0][0][0]=a[1];
for (int i = 0; i <= b[4]; i++) {
for (int j = 0; j <= b[3]; j++) {
for (int k = 0; k <= b[2]; k++) {
for (int z = 0; z <= b[1]; z++) {
//用t来表示到达第几格
t = 1+i*4 + j*3 + k*2 + z;
if (i)dp[i][j][k][z] = max(dp[i][j][k][z],dp[i - 1][j][k][z]+a[t]);
if(j)dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j-1][k][z]+a[t]);
if (k)dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k-1][z]+a[t]);
if(z)dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k][z - 1] + a[t]);
}
}
}
}
cout << dp[b[4]][b[3]][b[2]][b[1]];
return 0;
}