|
|
思路：
狀態數組 f[N][B][2]：
f[i][j][0] = { 現在處于第 i 個小時，之前一共休息了 j 個小時，第 i 個小時休息了。到現在為止獲得的最大點數 }
f[i][j][1] = { 現在處于第 i 個小時，之前一共休息了 j 個小時，第 i 個小時沒休息。到現在為止獲得的最大點數 }
由于是循環數組。所以就分開兩種情況：
1. 第 1 個小時沒休息
2. 第 1 個小時休息了
 #include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_N 4096
int in[MAX_N], N, B;
int dp[2][MAX_N][2], (*cur)[2], (*pre)[2];
__inline int max(int a, int b)
   {
 return a > b ? a : b;
 }
int main()
{
int i, j, val;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &B);
for (i = 0; i < N; i++)
scanf("%d", &in[i]);
// not using period #1
  for (i = 2; i < N; i++) {
pre = dp[i & 1];
cur = dp[(i + 1) & 1];
for (j = B - 2; j >= 0; j--) {
cur[j][1] = max(pre[j + 1][1] + in[i], pre[j + 1][0]);
cur[j][0] = max(pre[j][1], pre[j][0]);
 }
}
val = max(cur[0][1], cur[0][0]);
// using period #1
memset(dp, 0, sizeof(dp));
pre = dp[0];
pre[B - 2][1] = in[1];
for (i = 2; i < N; i++) {
pre = dp[i & 1];
cur = dp[(i + 1) & 1];
for (j = B - 2; j >= 0; j--) {
cur[j][1] = j == B - 2 ? 0 : max(pre[j + 1][1] + in[i], pre[j + 1][0]);
if (i == N - 1)
cur[j][1] += in[0];
cur[j][0] = max(pre[j][1], pre[j][0]);
}
}
val = max(val, cur[0][1]);
val = max(val, cur[0][0]);
printf("%d\n", val);
return 0;
}
|