BOJ 28129 - 2022 APC가 어려웠다고요?

BOJ 28129 - 2022 APC가 어려웠다고요?

그냥 DP 문제이다.

언뜻보면 시간복잡도가 불가능해보이지만 구간합 배열을 이용하면 $O(N^2)$에 채울 수 있다.

$dp[i][j]=i$ 번째 수가 $j$ 가 되는 경우의 수라고 할 때,

$dp[i][j]=\displaystyle \sum_{k=a_i}^{b_i}dp[i-1][k]$ 일 것이기 때문이다.

const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
int dp[3001][3001];
void solve() {
   int n, k;
   cin >> n >> k;
   vi a(n + 1), b(n + 1);
   for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
   for (int i = a[1]; i <= b[1]; i++) dp[1][i] = 1;
   for (int i = 2; i <= n; i++) {
      vi psum(3001);
      for (int j = 1; j <= 3000; j++) psum[j] = md(psum[j - 1] + dp[i - 1][j]);
      auto sum = [&](int l, int r) -> int {
         if (l > r) return 0;
         if (r > 3000) r = 3000;
         return md(psum[r] - (l > 0 ? psum[l - 1] : 0));
      };
      for (int j = a[i]; j <= b[i]; j++) {
         // 현재 수가 j가 되려면
         dp[i][j] = sum(j - k, j + k);
      }
   }
   int ans = 0;
   for (int i = a[n]; i <= b[n]; i++) {
      ans = md(ans + dp[n][i]);
   }
   cout << ans;
}