題意大概描述一下
有一只牛，在全天N小時內(nèi)花B小時睡覺，然后每一個時間點都有一個休息值，假設(shè)選擇在區(qū)間[s,e]內(nèi)休息，則第s個時間點不能夠獲得休息值。現(xiàn)在請安排這只牛的作息時間，使得他的休息值最大。
狀態(tài)dp[i][k][2]，i表示前i個小時，k表示休息了k個小時，最后一個狀態(tài)表示最后一個小時是否在休息。然后由于可以形成環(huán)（即第N個小時在休息，則第1個小時能夠獲得能量），需要2個DP。狀態(tài)轉(zhuǎn)移應(yīng)該很簡單吧~具體看程序。話說這題誰有nlogn的方法?感覺n
2好懸，常數(shù)還不小。。本機上跑了近1秒，用位運算、滾動數(shù)組等還有800ms，提交上去只有200ms。。看來poj的服務(wù)器很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