一定要记得初始化为-inf！！！
Description
在某个星球上，一天由N小时构成。我们称0-1点为第一个小时，1-2点为第二个小时，以此类推。在第i个小时睡觉能恢复Ui点体力。在这座星球上住着一头牛，它每天要休息B个小时，它休息的这B个小时可以不连续，可以分成若干段，但是在每一段的第一个小时不能恢复体力，从第二个小时开始才可以恢复体力。
为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。另外，因为时间是连续的，每天的第N个小时与下一天的第一个小时是相连的，这头牛只需要在N个小时内休息B个小时就够了。
请你给这头牛安排一个任务计划，使得它每天恢复的体力最多。
Sol
环形DP,第一反应是断环为链
所以这里就不讲断环为链了,讲一个另外的方法
考虑更简单的问题,假设第n个小时与第1个小时不是连续的,即问题是线性的
阶段与状态:f[i][j][0/1]表示1~i小时内睡了j个小时,第i小时睡了/没睡的最大恢复体力值
转移:f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])
f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i])
初始:f[i][j][0/1]=inf;f[1][1][1]=f[1][0][0]=0;
注意到,线性其实只比环少了一种情况,就是第1个小时与第n个小时都在睡觉的情况.
那么我们在线性解题的基础上加上这一情况即可
具体来说,先执行一遍DP,然后强行让牛在第n小时睡觉,即f[1][1][1]=a[1],再DP一次,用f[n][B][1]更新答案就可以了
还有,这题可以用滚动数组优化啊!
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define Rg register 5 #define il inline 6 #define db double 7 #define ll long long 8 #define mem(a,b) memset(a,b,sizeof(a)); 9 #define go(i,a,b) for(Rg int i=a;i<=b;++i) 10 #define yes(i,a,b) for(Rg int i=a;i>=b;--i) 11 using namespace std; 12 il int read() 13 { 14 int x=0,y=1;char c=getchar(); 15 while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} 16 while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} 17 return x*y; 18 } 19 const int N=3831; 20 int T,n,B,ans,a[N],f[N][N][2]; 21 il void dp() 22 { 23 go(i,2,n) 24 go(j,1,min(i,B)) 25 { 26 if(i!=j)f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); 27 if(j==1)f[i][j][1]=f[i-1][j-1][0]; 28 else f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i]); 29 } 30 } 31 int main() 32 { 33 T=read(); 34 while(T--) 35 { 36 n=read(),B=read(); 37 go(i,1,n)a[i]=read(); 38 mem(f,128);f[1][1][1]=f[1][0][0]=0; 39 go(i,1,n)f[i][0][0]=0; 40 dp();ans=max(f[n][B][0],f[n][B][1]); 41 mem(f,128);f[1][1][1]=a[1]; 42 go(i,1,n)f[i][0][0]=0; 43 dp();ans=max(ans,f[n][B][1]); 44 printf("%d ",ans); 45 } 46 return 0; 47 }