题意：0到10共11个位置，每秒有馅饼落下，gameboy在接，开始在位置5，每秒能移到一位，问最后gameboy能接住多少个。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1176
——>>设d[i][j]表示他第i秒在第j个位置所能接到的最大馅饼数（不加上第i秒之前的），递推即可。
当日的C++:
#include <iostream>
#include <string.h>
#include <cmath>using namespace std;const int maxn = 100000 + 10;
int num[maxn][12], d[maxn][12];int main()
{int n, x, T, i, j;while(cin>>n){if(!n) return 0;memset(num, 0, sizeof(num));memset(d, 0, sizeof(d));int max_t = -1;for(i = 0; i < n; i++){cin>>x>>T;num[T][x]++;max_t = max(max_t, T);}for(i = 0; i <= 10; i++)d[max_t][i] = num[max_t][i];for(i = max_t-1; i >= 0; i--)for(j = 0; j <= 10; j++){if(j == 0) d[i][j] = max(d[i+1][j], d[i+1][j+1]) + num[i][j];else if(j == 10) d[i][j] = max(d[i+1][j], d[i+1][j-1]) + num[i][j];else{d[i][j] = max(d[i+1][j], d[i+1][j+1]) + num[i][j];d[i][j] = max(d[i][j], d[i+1][j-1]+num[i][j]);}}cout<<d[0][5]<<endl;}return 0;
}
今天用的Java：
好多好多次忘记初始化数组，这次还是一样…………还要WA一次才AC……
import java.util.Scanner;
import java.lang.Math;
public class Main {static final int maxn = 100000 + 10;public static void main(String[] args) {Scanner cin = new Scanner(System.in);int n, d[][] = new int[maxn][15], a[][] = new int[maxn][15];while(cin.hasNextInt()){n = cin.nextInt();if(n == 0) break;for(int i = 0; i < maxn; i++)for(int j = 0; j < 15; j++)a[i][j] = 0;int time = -1;for(int i = 1; i <= n; i++){int x = cin.nextInt();int T = cin.nextInt();a[T][x]++;if(T > time) time = T;}for(int i = 0; i <= 10; i++) d[time][i] = a[time][i];for(int i = time-1; i >= 0; i--)for(int j = 0; j <= 10; j++){if(j == 0) d[i][j] = Math.max(d[i+1][j], d[i+1][j+1]) + a[i][j];else if(j == 10) d[i][j] = Math.max(d[i+1][j], d[i+1][j-1]) + a[i][j];else{d[i][j] = Math.max(d[i+1][j], d[i+1][j+1]) + a[i][j];d[i][j] = Math.max(d[i][j], d[i+1][j-1]+a[i][j]);}}System.out.println(d[0][5]);}cin.close();}
}