poj 2228 Naptime dp

這個題目的狀態還是比較好想的，dp[i][j]表示已經睡了i個時段，最後睡在j時段的最優值，但是需要處理環的情況，我的做法是算兩次，第一次不處理環，第二次強制性要求第一個時段需要睡，然後查看dp[m][n]+a[1]的值是否更優。

 
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;  
const int maxn=4e3+9;  
int a[maxn],dp[maxn][maxn];  
  
inline int max(int a,int b)  
{  
    if(a>b) return a;  
    else return b;  
}  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    int n,m;  
    while(scanf("%d %d",&n,&m)!=EOF)  
    {  
  
        for(int i=1;i<=m;i++)  
        for(int j=1;j<=n;j++)  
        dp[i][j]=0;  
        for(int i=1;i<=n;i++)  
        scanf("%d",&a[i]);  
        for(int k=2,ret;k<=m;k++)  
        {  
            ret=0;  
            for(int i=k;i<=n;i++)  
            {  
                dp[k][i]=max(ret,dp[k-1][i-1]+a[i]);  
                ret=max(ret,dp[k-1][i-1]);  
            }  
        }  
        int ans=0;  
        for(int i=m;i<=n;i++)  
        ans=max(dp[m][i],ans);  
  
        for(int i=1;i<=m;i++)  
        for(int j=1;j<=n;j++)  
        dp[i][j]=0;  
  
        dp[2][2]=a[2];  
        for(int k=3,ret;k<=m;k++)  
        {  
            ret=0;  
            for(int i=k;i<=n;i++)  
            {  
                dp[k][i]=max(ret,dp[k-1][i-1]+a[i]);  
                ret=max(ret,dp[k-1][i-1]);  
            }  
        }  
        if(m>=2)  
        ans=max(ans,dp[m][n]+a[1]);  
        cout<<ans<<endl;  
    }  
    return 0;  
}