|
|
思路：
由于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;
}
|