https://beta.atcoder.jp/contests/arc081
Typical DP Contest FGHIJ - omochan's diary
これのGとほとんど同じで、dp復元がくっついただけ。
でも1-originで逆から見ていくのでかなりこんがらがった。普通に0-originのstringを参照するときに-1をつければいいだけなんだけど。
dpも何を求めているか明確にしないまま実装入ったのもよくない。
あと写経ミスでnexを初期化する部分を間違ってしまった。これコンテストでやったらヤバイ。
int N; ll K; int nex[MAX_N][26]; ll dp[MAX_N]; int pv[MAX_N]; int E[26]; string str; void solve() { cin >> str; N = (int)str.size(); rep(i, 0, 26) str += char('a' + i); fill(E, E + 26, -1); rer(i, N + 27, 0) { //1-origin rep(j, 0, 26) nex[i][j] = E[j]; if(i) E[str[i - 1] - 'a'] = i; } fill(dp, dp + N + 1, inf); fill(pv, pv + N + 1, 1); rer(i, N + 1, 0) { rep(j, 0, 26) { assert(nex[i][j] != -1); pi p = pi(dp[nex[i][j]] + 1, str[nex[i][j] - 1] - 'a'); if(pi(dp[i], str[pv[i] - 1] - 'a') > p) { dp[i] = dp[nex[i][j]] + 1; pv[i] = nex[i][j]; } } } int at = 0; while(at < N + 1) { at = pv[at]; cout << str[at - 1]; } cout << "\n"; }