AOJ 0551 Icicles

問題

日本語なので説明はありません

Icicles

解法

これもDPって言うらしいです。誰かがDPだって言ってました。知りません。

つららが両端のつららよりも長ければ解け始めるってことからそのつららの長さに影響するのは両端だけ、つまり各つららに対して両端だけを見て行けばいい。

ここまで、聞いてやっと解けました。

dp[i]:= i番目のつつらが解けるまでの時間。初期値は0

長い順につららを見て行くと、 dp[i-1]とdp[i+1]が両方とも0ならdp[i]は両端よりも長い、つまり最初っから長くなっていくのでL-つららの長さがdp[i]となる。

それ以外ならdp[i-1]とdp[i+1]のうち長い方にL-つららの長さの和。

心臓に悪いコード

int N, in, L;
int dp[100002];
vector<pi>a;

int main(){
  scanf("%d%d", &N, &L);
  rep(i, N){
    scanf("%d", &in);
    a.PB(MP(in, i+1));
  }
  sort(a.begin(), a.end(), greater<pi>());

  rep(i, N){
    if(dp[a[i].S-1] == 0 && dp[a[i].S+1] == 0) dp[a[i].S] = L - a[i].F;
    else if(dp[a[i].S-1] > dp[a[i].S+1]) dp[a[i].S] = dp[a[i].S-1] + L - a[i].F;
    else if(dp[a[i].S+1] > dp[a[i].S-1]) dp[a[i].S] = dp[a[i].S+1] + L - a[i].F;
  }
  int res = 0;
  rep(i, N+2) res = max(res, dp[i]);

  printf("%d\n", res);
  return 0;
}

以前はコードを写経しても二度目にも問題が解けないことが多かった。最近は一週間ぐらい空いてもなんとかなったりしてる。