POJ 2228 Naptime 环形DP

「爱情、让人受尽委屈。」 2023-06-19 02:16 40阅读 0赞

**参考**  
[**https://blog.csdn.net/qq\_41925919/article/details/90267224**][https_blog.csdn.net_qq_41925919_article_details_90267224]

**先不考虑环的情况**  
**dp\[i\]\[j\]\[0\]:前i个时间间隔中，已经花费了j个间隔，取得的最大值，并且第i个间隔在休息  
dp\[i\]\[j\]\[1\]:前i个时间间隔中，已经花费了j个间隔，取得的最大值，并且第i个间隔不休息**

**转态转移**

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

最后的**结果** ans = max(dp\[N\]\[B\]\[0\],dp\[N\]\[B\]\[1\])

**考虑成环**  
由于N值过大，**将输入变成两倍接到后面**的做法不可取，tle

我们先令dp\[1\]\[1\]\[0\] = a\[1\],即在上一天最后一个时间段一定在sleep  
然后重新运行DP，这样除了最后一段时间和第一段时间，其他的时间段都是成环之后的正确值。  
**我们再来看第一段和最后一段**  
在最后一段sleep的情况下，第一段显然是正确的  
这是我们取 **ans = max(ans,dp\[N\]\[B\]\[0\])**,即最后一段时间一定在睡觉即可。

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <limits.h>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    int N,B;
    int a[3831];
    int dp[2][3031][2];
    
    void disp(){ 
        for(int i=0;i<=N;i++){ 
            for(int j=0;j<=B;j++){ 
                cout<<dp[i][j][0]<<" ";
                cout<<dp[i][j][1]<<" ";
                cout<<" ";
            }
            cout<<endl;
        }
    
    }
    int main()
    { 
    
        while( scanf("%d%d",&N,&B)!=EOF ){ 
            memset(dp,0x80,sizeof(dp));
            int ret = -1;
            for(int i=1;i <= N;i++){ 
                scanf("%d",&a[i]);
            }
            dp[1][0][1] = 0;
            dp[1][1][0] = 0;
    
            for( int i = 2;i <= N;i ++ ){ 
                for(int j = 0;j <= B;j ++){ 
                    dp[i&1][j][1] = max(dp[(i+1)&1][j][0],dp[(i+1)&1][j][1]);
                    if(j){ 
                        dp[i&1][j][0] = max(dp[(i+1)&1][j-1][0] + a[i],dp[(i+1)&1][j-1][1]);
                    }
                }
            }
    
            //debug(111)
            ret = max(dp[N&1][B][0],dp[N&1][B][1]);
    
    
            memset(dp,0x80,sizeof(dp));
            dp[1][1][0] = a[1];
            for(int i=2;i<=N;i++){ 
                for(int j=0;j<=B;j++){ 
                    dp[i&1][j][1] = max(dp[(i+1)&1][j][0],dp[(i+1)&1][j][1]);
                    if(j){ 
                        dp[i&1][j][0] = max(dp[(i+1)&1][j-1][0]+a[i],dp[(i+1)&1][j-1][1]);
                    }
                }
            }
            //disp();
            //ret = max(ret,dp[N&1][B][1]);
            ret = max(ret,dp[N&1][B][0]);
    
            cout<<ret<<endl;
        }
        return 0;
    }

![在这里插入图片描述][20191203194437954.png]

[https_blog.csdn.net_qq_41925919_article_details_90267224]: https://blog.csdn.net/qq_41925919/article/details/90267224
[20191203194437954.png]: https://img-blog.csdnimg.cn/20191203194437954.png