SRM 563 Div2 hard SpellCardsEasy
[問題文]
TopCoder Statistics - Problem Statement
カードの並びが与えられる。カード[i]にはlevel[i]とdamage[i]が書いてある。カード[i]を選んだとき、相手にdamage[i]のダメージを与え、カード[i]よりも右に置いてあるカードlevel[i] - 1枚を取り去る。(要は、遊○王の生贄システムみたいな感じ) 適切にカードを選んで与えられるダメージを最大化せよ。
[解法]
dp
とりあえず適当に区間dpを書いてみるが、駄目だと気付く。
カードをa -> b -> cと選ぼうにも、もしbがaの生贄対象ならそんな選び方はできないので、ビットdpしたい。でも制約的に無理。
あ~ なるほど。 こんなことも思いつかない俺はやはり頭が悪い。
そもそも、一番右から選んで行ったら、a -> b -> c(bはaの生贄)みたいな選び方もできる。結局どんなカードの選び方をしても生贄だから不可能という事はない。よって残りカードの枚数と選ぶカードの番号でdpすれば良い。
div2 hard、自力では大抵解けないしeditorial見て感動するためのものになってきてる。
int N; vector<int>le,da; int dp[100][100]; class SpellCardsEasy { public: int dfs(int p,int owed){ int res = 0; if(dp[p][owed] > 0) return dp[p][owed]; if(N - p == owed) return 0; res = dfs(p + 1,max(owed - 1,0)); if(owed + le[p] - 1 <= N - p - 1) res = max(res,da[p] + dfs(p + 1,owed + le[p] - 1)); return dp[p][owed] = res; } int maxDamage(vector <int> level, vector <int> damage) { N = level.size(); le = level,da = damage; memset(dp,0,sizeof(dp)); int res = dfs(0,0); return res; } };