Acwing P288 休息时间题解

Analysis

首先假设一天的第N小时与后一天的第一个小时不相连，这种情况下DP转移比较好想

dp[i][j][0/1]dp[i][j][0/1]表示

考虑一天的前i个小时，已经休息了j小时，且第i个小时是否在休息

那么有状态转移方程：

dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);

dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+a[i]);

初始化为dp[1][0][0]=dp[1][1][1]=0dp[1][0][0]=dp[1][1][1]=0，其余为-inf−inf

答案为max(dp[n][b][0],dp[n][b][1])max(dp[n][b][0],dp[n][b][1])

现在再考虑一天的第N小时与后一天的第一个小时相连

我们发现上述转移中，唯一没考虑到的情况只有第1个小时休息能获得体力

于是我们可以初始化dp[1][1][1]=U_1dp[1][1][1]=U1，转移方程与上述相同

那么答案为dp[n][b][1]dp[n][b][1](即强制最后一小时休息令第一小时能获得体力)，和前一次dp的答案比较即可得到最终结果

到此为止在这里已经可以AC，但是！！！如果我们拿到POJ上提交，你会发现自己疯狂MLE(POJ丧心病狂的Memory limit只有64M)

于是我们考虑用滚动数组优化空间

dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);

dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+a[i]);

因为dp[i][][]只与dp[i-1][][]有关，所以只要交替使用数组第0维和第1维，只保存上一次更新的dp数组，即可大幅优化空间

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define maxn 3830+10

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,b,ans;

 int u[maxn];

 int dp1[][maxn][],dp2[][maxn][];

 signed main()

 {

 //    freopen("naptime.in","r",stdin);

 //    freopen("naptime.out","w",stdout);

     n=read();b=read();

     for(int i=;i<=n;i++) u[i]=read();

     memset(dp1,,sizeof(dp1));

     dp1[][][]=dp1[][][]=;

     memset(dp2,,sizeof(dp2));

     dp2[][][]=u[];

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=min(i,b);j++)

         {

             dp1[i&][j][]=max(dp1[(i-)&][j][],dp1[(i-)&][j][]);

             if(j>=) dp1[i&][j][]=max(dp1[(i-)&][j-][],dp1[(i-)&][j-][]+u[i]);

             dp2[i&][j][]=max(dp2[(i-)&][j][],dp2[(i-)&][j][]);

             if(j>=) dp2[i&][j][]=max(dp2[(i-)&][j-][],dp2[(i-)&][j-][]+u[i]);

         }

     }

     ans=max(dp2[n&][b][],max(dp1[n&][b][],dp1[n&][b][]));

     write(ans);

     return ;

 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

巴特西

Acwing P288 休息时间题解

Analysis

最新文章

热门文章

巴特西

Acwing P288 休息时间 题解

Analysis

最新文章

热门文章

Acwing P288 休息时间题解