题意大概描述一下
有一只牛，在全天N小时内花B小时睡觉，然后每一个时间点都有一个休息值，假设选择在区间[s,e]内休息，则第s个时间点不能够获得休息值。现在请安排这只牛的作息时间，使得他的休息值最大。
状态dp[i][k][2]，i表示前i个小时，k表示休息了k个小时，最后一个状态表示最后一个小时是否在休息。然后由于可以形成环（即第N个小时在休息，则第1个小时能够获得能量），需要2个DP。状态转移应该很简单吧~具体看程序。话说这题谁有nlogn的方法?感觉n
2好悬，常数还不小。。本机上跑了近1秒，用位运算、滚动数组等还有800ms，提交上去只有200ms。。看来poj的服务器很NB
贴代码
1 # include <cstdio>
2 # include <cstring>
3 using namespace std;
4 # define max(a,b) ((a)>(b)?(a):(b))
5 int data[3850];
6 int dp[2][2][3850],dp1[2][2][3850];
7 int main()
8 {
9 // freopen("input.txt","r",stdin);
10 // freopen("output.txt","w",stdout);
11 int n,k;
12 scanf("%d%d",&n,&k);
13 for(int i=0;i<n;i++)
14 scanf("%d",data+i);
15 memset(dp,-1,sizeof(dp));
16 memset(dp1,-1,sizeof(dp1));
17 dp[0][0][0]=0;
18 dp[0][1][1]=0;
19 dp1[0][0][0]=0;
20 dp1[0][1][1]=data[0];
21 int res=0;
22 for(int i=1;i<n;i++)
23 {
24 memset(dp[i%2],-1,sizeof(dp[i%2]));
25 memset(dp1[i%2],-1,sizeof(dp1[i%2]));
26 dp[i%2][0][0]=0;
27 for(int j=1;j<=k;j++)
28 {
29 if(dp[(i-1)%2][0][j]!=-1)
30 dp[i%2][0][j]=max(dp[i%2][0][j],dp[(i-1)%2][0][j]);
31 if(dp[(i-1)%2][1][j]!=-1)
32 dp[i%2][0][j]=max(dp[i%2][0][j],dp[(i-1)%2][1][j]);
33 if(dp[(i-1)%2][0][j-1]!=-1)
34 dp[i%2][1][j]=max(dp[i%2][1][j],dp[(i-1)%2][0][j-1]);
35 if(dp[(i-1)%2][1][j-1]!=-1)
36 dp[i%2][1][j]=max(dp[i%2][1][j],dp[(i-1)%2][1][j-1]+data[i]);
37 if(dp1[(i-1)%2][0][j]!=-1)
38 dp1[i%2][0][j]=max(dp1[i%2][0][j],dp1[(i-1)%2][0][j]);
39 if(dp1[(i-1)%2][1][j]!=-1)
40 dp1[i%2][0][j]=max(dp1[i%2][0][j],dp1[(i-1)%2][1][j]);
41 if(dp1[(i-1)%2][0][j-1]!=-1)
42 dp1[i%2][1][j]=max(dp1[i%2][1][j],dp1[(i-1)%2][0][j-1]);
43 if(dp1[(i-1)%2][1][j-1]!=-1)
44 dp1[i%2][1][j]=max(dp1[i%2][1][j],dp1[(i-1)%2][1][j-1]+data[i]);
45 }
46 }
47 res=max(max(res,dp1[(n-1)%2][1][k]),max(dp[(n-1)%2][1][k],dp[(n-1)%2][0][k]));
48 printf("%d\n",res);
49 return 0;
50 }
51