問題概要
- $m$色のうちどれかの色のブロックが$n$個降ってくる。各ブロックについて積むか積まないか選ぶ。
- 各色毎に得点が定まっている。同じ色を繋げるとコンボボーナス、全色使用するとボーナス。（負の場合もある）
- 最高得点を求めよ
- 制約：$n \le 5000, m \le 10$
- リンク
最初に考えたこと
- $O(n^2)$が通りそうだけど微妙そう。もし$O(n^2)$なら区間を決めてモニョモニョするのか？しかし厳しそうなので$O(n)$っぽい。とするとDPか何か？
- $m$が小さいので使った色の情報を持たせられそう。DPだとすると持たせる状態は、
- 今見ているブロック($O(n)$)
- 今の色の使用状況($O(2^m)$,bitで持つ)
- 何連続同じ色(コンボボーナス,$O(n)$)
- として
dp[i][bit][ComboLength] = HighScoreみたいな感じ - これだと$O(n^2 * 2^m)$で間に合わないので何とか$O(n)$にしたい
- コンボボーナスは長さが
1増えるとY増えるだけなので直前の色だけ見ればええやん（長さの情報は不要）
考察
-
DPで解く
-
持たせる状態は、
- 今見ているブロック($O(n)$)
- 今の色の使用状況($O(2^m)$)
- 最後に使った色($O(m)$)
-
として
dp[i][bit][LastColor] = HighScoreみたいな感じ -
$i+1$番目のブロック(色は
NowColor)を使うときの遷移は、-
dp[i+1][bit | 1<<NowColor][NowColor]へ配る感じで書いた（貰うDPでもいいけど） -
LastColor == NowColorならコンボボーナス発生(bonus+=Y) -
bit | 1<<NowColorが最新の色の使用状況。bitの各ビットが全て立っておらず、bit | 1<<NowColorで全てのビット（正確には下からmbit）が立っていれば、その時点で初めて全色を使用したことになるので、全色使用ボーナス発生(bonus+=Z) -
dp[i+1][bit | 1<<NowColor][NowColor]とdp[i][bit][LastColor] + bonusを比較して大きくなっていれば更新
-
-
$i+1$番目のブロックを使わないときの遷移は、
-
dp[i+1][bit][LastColor]とdp[i][bit][LastColor]を比較して大きくなっていれば更新
-
-
dpテーブルを
dp[0][0][0]だけ$0$で初期化、それ以外は-INFとしておく（後述） -
計算量$O(nm2^m)$
反省
- 初め、深く考えずに全て
-Yでdpテーブルを初期化していた（サンプルが合ったので） - これはまずい点が二つあり、まずブロックを一つも取らない状態をカバーできていない（当然0になるはずなので）
- 次に、ありえない遷移を容認していることになる
- 例えば、「一つ目のブロックを見ているときにすでに$m-1$色$(m>2)$使っているとして、そのブロックを採用すると全色ボーナス発生w!」みたいなパターンを許してしまっている
- 二つ目は簡単で、#考察 で述べたように初期状態としてありえないもの（
dp[0][(1<<m)-1][m]など）を$- \infty$で初期化しておくことで無視できる。 - 一つ目は少し工夫が必要。解決策の一つとしては、直前に使った色に「無色」を追加することで、これをまだブロックを一つも使っていない状態とみなせる。
- こうすると、まだ一つもブロックを見ていない状態では無色の場合のみがありえて（
dp[0][0][0] = 0）、それ以外はありえないので-INFで初期化。
- こうすると、まだ一つもブロックを見ていない状態では無色の場合のみがありえて（
- サンプルに合わせにいってはダメ(戒め)
実装
#include "bits/stdc++.h"
using namespace std;
const int INF = 1<<29;
void solve()
{
int n, m, Y, Z;
string BlockString;
cin >> n >> m >> Y >> Z;
vector<int> ColorBonus(m+1);
map<char, int> ColorToInt;
for (int i = 0; i < m; i++)
{
char c;int p;
cin >> c >> p;
ColorBonus[i+1] = p;
ColorToInt[c] = i+1;
}
cin >> BlockString;
//3次元のdpテーブル
//vector じゃない方が宣言は見やすいんですけど初期化が楽なのでvectorを使っています
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(1<<m, vector<int>(m+1, -INF)));
dp[0][0][0] = 0;
int ans = 0;
//i番目のブロックに遷移する(1-indexed)
for (int i = 0; i < n; i++)
//下からx番目のbitが立っている:=x番目の色を使った(無色を除くので1-indexed)
for (int bit = 0; bit < (1<<m); bit++)
//0番目:=無色
for (int LastColor = 0; LastColor < m+1; LastColor++)
{
//i番目のブロックを使う
int NowColor = ColorToInt[BlockString[i]], bonus = ColorBonus[NowColor], Nextbit = bit | 1<<(NowColor-1);
if (LastColor == NowColor) bonus += Y;
if (bit != (1<<m)-1 && Nextbit == (1<<m)-1) bonus += Z;
dp[i+1][Nextbit][NowColor] = max(dp[i+1][Nextbit][NowColor], dp[i][bit][LastColor] + bonus);
//i番目のブロックを使わない
dp[i+1][bit][LastColor] = max(dp[i+1][bit][LastColor], dp[i][bit][LastColor]);
ans = max({ans, dp[i+1][Nextbit][NowColor], dp[i+1][bit][LastColor]});
}
cout << ans << endl;
}
int main()
{
solve();
//cout << "yui(*-v・)yui" << endl;
return 0;
}
最後に
- 試験勉強からの逃避でゆゆ式MADを見ながら書き上げました
- 現在クリスマス当日の午前４時半くらいですが、サンタさんが現れる気配はないです...
- このdp思いついて通せたのは成長だな、と思って記事を書きました
- 無色を導入しなくてもいい方法があればコメントなどで知らせてもらえると勉強になります
- メリークリスマス