HDU1176

[java] 
package DP; 
 
import java.util.*; 
 
public class HDU1176 { 
    // arr[i][j]表示第i秒第j個位置的餡餅的數目。 
    static int[][] arr; 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        int n; 
        while (sc.hasNext()) { 
 
            arr = new int[100001][11]; 
             
            n = sc.nextInt(); 
            if (n == 0) 
                break; 
 
            int maxt = 0;// 最大時間。 
 
            while (n-- > 0) { 
                int x = sc.nextInt(); 
                int t = sc.nextInt(); 
                arr[t][x]++; 
 
                if (t > maxt) 
                    maxt = t; 
            } 
 
            for (int i = maxt - 1; i >= 0; i--) { 
                for (int j = 1; j <= 9; j++) { 
                    arr[i][j] += getMax(arr[i + 1][j - 1], arr[i + 1][j], arr[i + 1][j + 1]); 
                } 
                arr[i][0] += Math.max(arr[i + 1][0], arr[i + 1][1]); 
                arr[i][10] += Math.max(arr[i + 1][10], arr[i + 1][9]); 
 
            } 
            System.out.println(arr[0][5]); 
 
        } 
    } 
 
    private static int getMax(int a, int b, int c) { 
        int max1; 
        max1 = a > b ? a : b; 
        max1 = max1 > c ? max1 : c; 
        return max1; 
 
    } 
}