るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

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したい。でも制約的に無理。

SRM 563 - TopCoder Wiki を読む。

あ~ なるほど。 こんなことも思いつかない俺はやはり頭が悪い。

そもそも、一番右から選んで行ったら、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;
  }
};