【題目敘述】https://vjudge.net/problem/HDU-1176
【解題想法】DP
- cake[100000][11]：紀錄每個時間每個位置上，掉落的餡餅數目
- dp[100000][11]：紀錄每個時間每個位置上，累積撿到的最多餡餅數目
- 因為每秒鐘只能移動一米，因此更新dp[t][i]時只需考慮三種情形：
- dp[t-1][i-1]：上一秒人在 i – 1 的位置，向右移動
- dp[t-1][i]：上一秒人在 i 的位置，不動
- dp[t-1][i+1]：上一秒人在 i + 1 的位置，向左移動
- 頭尾 i = 0, i = 10 的情況要分開考慮。
#include <iostream>
#include <cstring>
using namespace std;
int cake[100000][11]; //每個時間每個位置上，掉落的餡餅數目
int dp[100000][11]; //每個時間每個位置上，累積撿到的餡餅數目
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x, T;
while (cin >> n && n){
memset(cake, 0, sizeof(cake));
memset(dp, -1, sizeof(dp));
int endTime = 0;
for (int i=0; i<n; i++){
cin >> x >> T;
cake[T][x]++;
endTime = max(endTime, T);
}
dp[0][5] = 0; //开始时gameboy站在5这个位置
for (int i=1; i<=endTime; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) +cake[i][0];
for (int j=1; j<10; j++){
dp[i][j] = max(max(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]) + cake[i][j];
}
dp[i][10] = max(dp[i-1][10], dp[i-1][9]) +cake[i][10];
}
int mx = 0;
for (int i=0; i<=10; i++){
mx = max(mx, dp[endTime][i]);
}
cout << mx << '\n';
}
return 0;
}