![見出し画像](https://assets.st-note.com/production/uploads/images/129399176/rectangle_large_type_2_eb9d74d72c81e7aaa58347199eb7ae9c.png?width=1200)
今日の精進-DP(AtCoder ABC222-D)
今日、解き直した問題は AtCoder ABC222-D「Between Two Arrays」です。DPはいつまでも苦手です。
問題
ポイント
適当な例( $${N=3}$$ くらいで)を作って、実際に整数列 $${C}$$ を作ってみると、1個前の数字によりけりだなと思い、DPを検討する。
dp[ i ][ j ] を i 個目までみていて、i 個目が j の時に作れる整数列の数が入ると定義する。
という感じで、二次元のDPでいけそうなので、紙に表を書いてみる。
ACしたコード
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;
int main() {
int N;
cin >> N;
vector<int> a(N);
rep(i, N) { cin >> a[i]; }
vector<int> b(N);
rep(i, N) { cin >> b[i]; }
vector<vector<mint>> dp(N+1, vector<mint>(3001, 0));
dp[0][0] = 1;
rep(i, N) {
if (i == 0) {
for(int j = a[0]; j <= b[0]; ++j) {
dp[1][j] = 1;
}
} else {
for(int j = 0; j < 3000; ++j) {
dp[i][j+1] += dp[i][j];
}
for(int j = a[i]; j <= b[i]; ++j) {
dp[i+1][j] += dp[i][j];
}
}
}
mint ans = 0;
rep(i, 3001) {
ans += dp[N][i];
}
cout << ans.val() << endl;
return 0;
}
上のコードの dp[ i ][ j + 1 ] += dp[ i ][ j ] は累積和っぽい感じ。
1つ前の行の累積和をとってから、次の行に渡すというイメージ。
なかなか難しいな。
この記事が気に入ったらサポートをしてみませんか?