这个题目的状态还是比较好想的，dp[i][j]表示已经睡了i个时段，最后睡在j时段的最优值，但是需要处理环的情况，我的做法是算两次，第一次不处理环，第二次强制性要求第一个时段需要睡，然后查看dp[m][n]+a[1]的值是否更优。
#include
#include
#include
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<
|