D - サプリメント
dp[i] := i個目まで食べる組み合わせとする
最後の日に添字iを食べる組み合わせは
i
i-1,i
i-2,i-1,i
i-3,i-2,i-1,i
…
のように分けられる
また、上はdp[i-1],dp[i-2],dp[i-3]…
である
この時添字i以前で同じでない最長の区間を足し合わせればdp[i]が求まる
Submission #3782329 - AtCoder Beginner Contest 017
mint dp[k5];
signed main() {
cin >> N >> M;
addAll(A, N);
dp[0] = dp[1] = 1;
vb aru(k5);
aru[A[0]] = 1;
int sum = 1;
int li = 0;
rep(i, 1, N) {
//左端は自分と同じ数
sum += dp[i];
while (aru[A[i]]) {
sum -= dp[li];
aru[A[li++]] = 0;
}
dp[i + 1] = sum;
aru[A[i]] = 1;
}
cout << dp[N] << endl;
return 0;
}
