【題解】Codeforces 1324E. Sleeping Schedule

【題目敘述】http://codeforces.com/contest/1324/problem/E
【解題想法】DP

#include <bits/stdc++.h>
using namespace std;
 
int n, h, l, r, dp[2005][2005], a[2005];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> h >> l >> r;
    for (int i = 0; i <= n; i++){
        for (int j = 0; j < h; j++){
            dp[i][j] = -1e9;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        for (int j = 0; j < h; j++){
            int tmp = (j+a[i])%h;
            dp[i][tmp] = max(dp[i][tmp], dp[i-1][j]+(l <= tmp && tmp <= r));
            tmp = (j+a[i]-1)%h;
            dp[i][tmp] = max(dp[i][tmp], dp[i-1][j]+(l <= tmp && tmp <= r));
        }
    }
    int mx = 0;
    for (int i = 0; i < h; i++){
        mx = max(mx, dp[n][i]);
    }
    cout << mx << "\n";
}
分享本文 Share with friends