問題#
カメのボードゲームのボードは $N$ 個のマスからなる一列で、各マスにはスコア（非負整数）が置かれています。ボードの第 $1$ マスは唯一のスタート地点であり、第 $N$ マスはゴールです。ゲームでは、プレイヤーがカメのコマをスタート地点からゴールまで移動させることが求められます。
カメのボードゲームには $M$ 枚の移動カードがあり、$4$ 種類の異なるタイプに分かれています（$M$ 枚のカードには必ずしも全ての $4$ 種類のカードが含まれているわけではありません、例を参照）。各タイプのカードには $1,2,3,4$ のいずれかの数字が書かれており、そのカードを使用するとカメのコマは対応するマス数だけ前進します。ゲーム中、プレイヤーは毎回、未使用の移動カードの中から 1 枚を選び、カメのコマを対応するマス数だけ前進させる必要があります。各カードは一度しか使用できません。
ゲーム中、カメのコマは自動的にスタート地点のスコアを獲得し、その後の移動中に各マスに到達するたびに、そのマスのスコアを獲得します。プレイヤーの最終的なゲームスコアは、カメのコマがスタート地点からゴールまでの過程で通過した全てのマスのスコアの合計です。
明らかに、異なる移動カードの使用順序によって最終的なゲームスコアは異なります。小明は最も高いスコアを得るためのカードの使用順序を見つけたいと考えています。
さて、ボード上の各マスのスコアと全ての移動カードが与えられたとき、小明が得られる最大スコアはいくらか教えてくれますか？
$100%$ のデータでは $1≤N≤350,1≤M≤120$ であり、$4$ 種類の移動カードの各種類の枚数は $40$ 枚を超えません；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。
解法#
f[i][j][k][l] を、前進 1 マスのカードを $i$ 枚、2 のカードを $j$ 枚、3 のカードを $k$ 枚、4 のカードを $l$ 枚選択したときに得られる最大利益とします。
遷移を行います。
問題#
1.line55、1 を加える必要があります。
コード#
#include<bits/stdc++.h>
using namespace std;
const int N = 355;
int a[N], n, m;
int num[5];
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
int f[42][42][42][42];
int main()
{
memset(f, -0x3f, sizeof f);
n = read(), m = read();
for(int i = 1;i <= n;i++)
{
a[i] = read();
}
int t;
for(int i = 1;i <= m;i++)
{
t = read();
num[t]++;
}
f[0][0][0][0] = a[1];
int ans = -0x7f7f7f7f;
for(int i = 0;i <= num[1];i++)
{
for(int j = 0;j <= num[2];j++)
{
for(int k = 0;k <= num[3];k++)
{
for(int l = 0;l <= num[4];l++)
{
if(i == j && j == k && k == l && i == 0) continue;
int x = 1 + i + 2 * j + 3 * k + 4 * l;
if(x > n) continue;
if(i - 1 >= 0)
f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[x]);
if(j - 1 >= 0)
f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[x]);
if(k - 1 >= 0)
f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[x]);
if(l - 1 >= 0)
f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[x]);
ans = max(ans, f[i][j][k][l]);
}
}
}
}
printf("%d", ans);
return 0;
}