SP283 NAPTIME - Naptime
题意：
在某个星球上，一天由N小时构成。我们称0-1点为第一个小时，1-2点为第二个小时，以此类推。在第i个小时睡觉能恢复Ui点体力。在这座星球上住着一头牛，它每天要休息B个小时，它休息的这B个小时可以不连续，可以分成若干段，但是在每一段的第一个小时不能恢复体力，从第二个小时开始才可以恢复体力。 为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。另外，因为时间是连续的，每天的第N个小时与下一天的第一个小时是相连的，这头牛只需要在N个小时内休息B个小时就够了。 请你给这头牛安排一个任务计划，使得它每天恢复的体力最多。
输入格式： 第一行一个整数T表示有T组测试数据 对于每一组测试数据，第一行为两个整数N与B，接下来N行每行一个整数Ui。（2 <= B < N <= 3830 , 0 <= Ui <= 200000）
输出格式： 对于每组输入数据，对应一行输出一个整数，表示答案。（注意：两组输出之间没有空行）
我们可以发现一些很显然的性质：如果第一小时的体力值能够恢复，当且仅当第n小时和第一小时都在睡觉，然而我们并不确定第n小时究竟是不是睡觉，所以就不知道应该怎样给第一天初始值了，但是如果我们将这一限制去除，那么无论第n小时在不在睡觉第一小时都不会回复体力值，这样就可以进行第一次的dp，但是样就会出现一个问题，如果第一小时和第n小时都在睡觉，那么就会少U[1]点体力值，这样的话我们就可以强制令第一小时和第n小时都在睡觉，再进行一次dp并且把U[1]加进去，两次dp取最大值，就是答案了。
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#define maxn 4005
using namespace std; inline int read()
{
char c=getchar();
int x=,res=;
while(c<''||c>'')
{
if(c=='-')
x=-;
c=getchar();
}
while(c>=''&&c<='')
{
res=res*+(c-'');
c=getchar();
}
return x*res;
} int t,n,m,ans;
int a[maxn];
int f[maxn][maxn][],dp[maxn][maxn][]; int main()
{
t=read();
while(t--)
{
ans=;
n=read();m=read();
for(int i=;i<=n;i++)
{
a[i]=read();
}
memset(f,-0x3f,sizeof(f));
f[][][]=;f[][][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(j>) f[i][j][]=max(f[i-][j-][],f[i-][j-][]+a[i]);
f[i][j][]=max(f[i-][j][],f[i-][j][]);
}
}
ans=max(f[n][m][],f[n][m][]);
memset(f,-0x3f,sizeof(f));
f[][][]=a[];
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(j>) f[i][j][]=max(f[i-][j-][],f[i-][j-][]+a[i]);
f[i][j][]=max(f[i-][j][],f[i-][j][]);
}
}
ans=max(ans,f[n][m][]);
printf("%d\n",ans);
}
return ;
}