|
|
思路：
由于W的值 <= 30，比较小，所以这题可以用动态规划来做。
首先要把连续同一个数字一次处理。
dp[i] = {走了 i 次以后，得到的最大的苹果数目}。这个数组的大小为 W。
走了奇数次以后，一定位于树2下面。
走了偶数次以后，一定位于树1下面。
假设当前是在第 t 时刻掉了 cnt 个苹果下来。val 表示哪棵树掉的苹果，则执行下面的操作更新数组就可以了。
  if (val == 1)  {
 for (i = 0; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 1; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
} else {
for (i = 1; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 0; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
 }
转移方程就是这个，还是挺简单的。
因为数据弱，代码 0ms ac了。
完整代码：
 #include <stdio.h>
int T, W, dp[35], t;
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
__inline void calc(int val, int cnt)
{
int i;
  if (val == 1) {
for (i = 0; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 1; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
} else {
for (i = 1; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 0; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
 }
t++;
}
int main()
{
int i, pre, cnt;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &T, &W, &pre);
cnt = 1;
while (--T) {
scanf("%d", &i);
if (i == pre) {
cnt++;
continue;
}
calc(pre, cnt);
cnt = 1;
pre = i;
}
calc(pre, cnt);
cnt = 0;
for (i = 0; i <= W; i++)
cnt = max(cnt, dp[i]);
printf("%d\n", cnt);
return 0;
}
|