[ABC261] D - Flipping and Bonus
[Q] https://atcoder.jp/contests/abc261/tasks/abc261_d
・考察
1. DP[index][カウント数] で管理する。
2. DP[N][0~N]のうち、最大値が答え。
Q. 裏のときにボーナス1は入る？
A. 入らない。問題ちゃんと読めばよかった。連続ボーナスじゃなくてカウントボーナス。
俺はいつだって、もらうDP信者です。
Q. ex1
N=6 M=3
X[]: 2 7 1 8 2 8
bonus:
2 10
3 1
5 5
次のようなDP表が作れればいい
DP[index][カウント数]で管理する。
DP[1][0] = 0 : 裏
DP[1][1] = 2 : 表
DP[2][0] = 2 : 裏裏, 表裏のうち最大
DP[2][1] = 7 : 裏表 = DP[1][0] + X[1]
DP[2][2] = 19 : 表表 = DP[1][1] + X[2] + C[2]
DP[3][0] = 19 : DP[2][0~2]から裏を引く状態
DP[3][1] = 3 : DP[2][0] + X[2]
DP[3][2] = 18 : DP[2][1] + X[2] + C[2]
DP[3][3] = 21 : DP[2][2] + X[2] + C[3]
...
DP[6][0]:39
DP[6][1]:37
DP[6][2]:41
DP[6][3]:48
DP[6][4]:32
DP[6][5]:42
DP[6][6]:44
DP[6][3] = 48が最大.実装
ll DP[5050][5050]; // DP[index][cnt] 表が何回連続してるか
ll N, M;
ll X[5050];
ll C[5050]; // C[cnt] = bonus
int main(){
cincout();
cin >> N >> M;
rep(i, N) cin >> X[i];
rep(i, M){
ll c, y;
cin >> c >> y;
C[c] = y;
}
rep(i, N){
for(ll j=0; j<=i; ++j){
/*
i=2でDP[3][j]をみるとき、
・裏の遷移
DP[3][0] = DP[2][0] ~ DP[2][2]
・表の遷移
DP[3][1] = DP[2][0]+X+C
DP[3][2] = DP[2][1]+X+C
DP[3][3] = DP[2][2]+X+C
i=2のときj=0~2を動けばいい
*/
// もらうDP
// 裏が出た場合
chmax(DP[i+1][0], DP[i][j]); // コンボ数0に渡す
// 表が出た場合 表+コンボボーナス
chmax(DP[i+1][j+1], DP[i][j] + X[i] + C[j+1]); // コンボ数j->j+1に渡す
}
}
ll ans = 0;
rep(i, N+1){ // DP[6][0~6]のmax
chmax(ans, DP[N][i]);
}
cout << ans << endl;
}