【POJ2228】Naptime

一时失言乱红尘 2021-12-12 09:07 199阅读 0赞

关于环形dp的处理，我采用的办法是，把整个问题分成两个问题。

首先我们简化一下问题，假设这个问题不是环形的，那么我们定义f\[i\]\[j\]\[1\]表示前i个小时休息了j小时，且第i小时正在休息，获得的体力最大值。定义f\[i\]\[j\]\[0\]表示前i个小时休息了j小时，且第i小时不在休息，获得的体力最大值。显然有f\[i\]\[j\]\[0\]=max(f\[i-1\]\[j\]\[1\],f\[i-1\]\[j\]\[0\]),f\[i\]\[j\]\[1\]=max(f\[i-1\]\[j-1\]\[0\],f\[i-1\]\[j-1\]\[1\]+val\[i\]).初始化f\[1\]\[0\]\[0\]=f\[1\]\[1\]\[1\]=0,其余为负无穷,目标为max(f\[n\]\[m\]\[1\],f\[n\]\[m\]\[0\]).

简化问题中，每天的第一个小时是每天的开始，一定不能睡觉。所以一次dp结束之后，我们还需要解决每天的第一个小时入睡的情况，为了解决这种情况，我们使第1个小时与第n个小时都在睡觉，按照上述的方法求解即可，此时初始化f\[1\]\[1\]\[1\]=val\[1\],其余为负无穷，目标为f\[n\]\[m\]\[1\]

我们执行两次dp，取最优即可。

另外，n的规模为4000，而状态转移时阶段i只能由i-1转移而来，所以我们可以用滚动数组减少空间的浪费。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <algorithm>
     5 using namespace std;
     6 int n,m,a[4000],f[3][4000][3],ans;
     7 int main() {
     8     scanf("%d%d",&n,&m);
     9     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    10     if(!m) {
    11         puts("0");
    12         return 0;
    13     }
    14     memset(f,0xcf,sizeof(f));
    15     f[1&1][0][0]=0;
    16     f[1&1][1][1]=0;
    17     for(int i=2;i<=n;i++) {
    18         for(int j=0;j<=m;j++) {
    19             f[i&1][j][0]=max(f[i-1&1][j][0],f[i-1&1][j][1]);
    20             if(j>0) f[i&1][j][1]=max(f[i-1&1][j-1][0],f[i-1&1][j-1][1]+a[i]);
    21         }
    22     }
    23     ans=max(f[n&1][m][1],f[n&1][m][0]);
    24     memset(f,0xcf,sizeof(f));
    25     f[1&1][1][1]=a[1];
    26     for(int i=2;i<=n;i++) {
    27         for(int j=0;j<=m;j++) {
    28             f[i&1][j][0]=max(f[i-1&1][j][0],f[i-1&1][j][1]);
    29             if(j>0) f[i&1][j][1]=max(f[i-1&1][j-1][0],f[i-1&1][j-1][1]+a[i]);
    30         }
    31     }
    32     ans=max(ans,f[n&1][m][1]);
    33     printf("%d\n",ans);
    34     return 0;
    35 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/10700991.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211211/1981c4d133a549eebfe753384a83c5f4.png