codeforces 627 div3 E. Sleeping Schedule （dp）

题意：

n，h，l，r，给n个时间间隔，从0开始睡觉，一天共有h小时，每次睡ai 或者 ai-1段时间。（n<2000,h<2000)

如果在l 和 r段时间入睡那么满意度+1,问满意度最高多少？

题解：

最近都在做dp的题，这题一看数据范围就知道是个二维关于n和h的dp，打到E题还剩下1小时感觉这题稳了，状态转移方程也很快推了出来。有点像01背包，设dp[i][j]为前i个当前时间为j的最大满意度，

前i-1选择a[i]到dp[i][j]，就是dp[i-1][(j-a[i]+h)%h]，

或者选a[i]-1,就是dp[i-1][(j-(a[i]-1)+h)%h]。

dp[i][j]=max(dp[i-1][(j-(a[i]-1)+h)%h],dp[i-1][(j-a[i]+h)%h])；

if(j>=l&&j<=r) dp[i][j]++;

就是对不合法状态不知道怎么处理，看了题解才知道，一开始dp全赋值-1，就是不合法的状态。

dp[0][0]赋值为0，以便i=1转移。

dp这种东西果然做多了就很有感觉，继续加油吧！

代码：

#include<bits/stdc++.h>
#define endl '
'
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define check system("pause")
#define all(x) (x).begin(),(x).end()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lowbit(a) ((a)&-(a))
#define INF 0x3f3f3f3f
const ll mod = 1e9+7;
const int N = 2e3+20;
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define mes(p,b) memset(p,b,sizeof(p))
#define sz(x) int(x.size())
ll dp[N][N],n,h,l,r,a[N],ans=0;
int main()
{
      ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>h>>l>>r;
    rep(i,1,n) cin>>a[i];
    mes(dp,-1); 
    dp[0][0]=0;
    rep(i,1,n)
        rep(j,0,h-1){
            if(dp[i-1][(j-(a[i]-1)+h)%h]!=-1) dp[i][j]=dp[i-1][(j-(a[i]-1)+h)%h];
            if(dp[i-1][(j-a[i]+h)%h]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]+h)%h]);
            if(dp[i][j]!=-1&&j>=l&&j<=r) dp[i][j]++;
        }
    rep(i,0,h-1)
    ans=max(ans,dp[n][i]);
    cout<<ans;
      return 0;
      
}

codeforces 627 div3 E. Sleeping Schedule （dp）

相关推荐