先考虑如果只有一天，那么该怎么做。
设(f[i][j][1])表示前(i)个小时睡了(j)个小时并且第(j)个小时正在睡觉时的最大体力，(f[i][j][1])表示前(i)个小时睡了(j)个小时并且第(j)个小时没在睡觉时的最大体力。
则有
[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])
]
边界条件:(f[1][0][0]=f[1][1][1]=0)
答案:(max(f[n][b][0],f[n][b][1]))
然后，现在两天是连着的，唯一的区别就是第一个小时可以睡着。
于是，令(f[1][1][1]=U_1)，然后再跑一遍DP，把(ans)和(f[n][b][1])取最大值就行了。
为什么只与(f[n][b][1])取最大值呢？
因为这里把(f[1][1][1])赋值为了(U_1)，那么我们默认就是第一个小时进入了熟睡状态，所以上一天最后一个小时必须开始睡觉才行。
因为SPOJ的空间限制比较大，我就没用滚动数组了。
#include <cstdio>
inline int max(int a, int b){
return a > b ? a : b;
}
inline int min(int a, int b){
return a < b ? a : b;
}
const int MAXN = 4000;
int f[MAXN][MAXN][3], w[MAXN];
int n, m, T;
int main(){
scanf("%d", &T);
while(T--){
int ans = 0;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
f[1][0][0] = f[1][1][1] = 0;
for(int i = 2; i <= n; ++i){
for(int j = 1; j <= min(i, m); ++j){
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]);
if(j != 1) f[i][j][1] = max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + w[i]); //第一个小时不加体力
}
}
f[1][1][1] = w[1]; f[1][0][0] = 0; //边界
ans = max(f[n][m][1], f[n][m][0]);
for(int i = 2; i <= n; ++i)
for(int j = 1; j <= min(i, m); ++j){
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]);
if(j != 1) f[i][j][1] = max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + w[i]);
}
ans = max(ans, f[n][m][1]);
printf("%d
", ans);
}
return 0;
}