- /* 动态规划满足整体最优解可以由子结构局部最优解推出，从小到大一步一步推往前或者往后推。
- *
- * 实际上做题的时候，就是把每种情况下小的最优解存起来 ，供下一个更大规模的局部去选择最优解，然后再存起来这种更大规模的各种情况下最优解。
- * 一层一层存起来去推，最后就能求得最后你需要规模的最优值
- *
- * 此题dp【】【】数组就是用来存局部最优解的
- * dp【n】【1,2,3.....】就是n规模1 ，2 ，3......这几种位置情况各自能再接到最多的馅饼（明显这里还能接再得到最多馅饼就是最优意思）
- * dp【n-1】【1,2,3......】就是扩大规模变为n-1后1,2,3....这几种位置情况下还能在接到的馅饼
- * （n-1之所以比n规模大，是考虑实际情况，n-1时刻到endTime时刻明显比n增加了1，时间长还能接到的饼多，当然算是规模大了）
- * （求最优n规模必须经过最优n-1规模，说明就存在最优子结构关系）
- *
- *
- * dp二维数组具体表示 从t时刻起到最后一刻时间，x位置还能再接的最多的饼数（注意是还能再接，且是最多）,题目总共有是一个位置，故x为11
- *
- * exactly 二维数组 存 x位置，在t时刻，头顶上会掉多少个饼
- *
- * dp最优子结构性质公式:dp[x,t]=exactly[x,t] + max{dp[x,t+1],dp[x-1,t+1],dp[x+1,t+1]}
- */
- import java.util.Arrays;
- import java.util.Scanner;
- public class DP_FreePie {
- public static void main(String[] args) {
- Scanner scan = new Scanner(System.in);
- int n = scan.nextInt();
- int exactly [][] = new int[11][n]; //有十一个位置
- int dp [][] = new int[11][n];
- int x ,t ,endTime = 0;
- for(int i = 0; i < n; i++) {
- Arrays.fill(exactly[i], 0);
- Arrays.fill(dp[i], 0); //给两个二维数组赋初值为0
- }
- for(int i = 0; i < n; i++) {
- x = scan.nextInt();
- t = scan.nextInt();
- exactly[x][t]+= 1; //将馅饼掉落数据输入，
- if (t > endTime) {
- endTime = t; //记录最后掉馅饼的时间endTime
- }
- }
- /*
- * 接下来就是一层一层求dp【】【】了
- * 根据最优子结构性格的公式，我们是从最后的最优子结构往前推的
- * 即最先求的应该是最后的时刻endTime他每个位置的最优值
- */
- for(int i = 0;i <= 10; i++) {
- dp[i][endTime] = exactly[i][endTime];
- }
- for(int time = endTime-1; time >= 0; time--) { //到最后的时间变长，规模变大
- int particalMax = 0;
- for(int position = 0; position <= 10; position++) { //此时刻每一个位置的情况的最优值
- particalMax = dp[position][time+1];
- /*
- * 这里说一下，要考虑边界的问题，例如在n时刻0位置，求它的最优值即要看n+1时刻它的-1,0,1位置的最优值
- * 很显然时间time是从倒数第二秒开始在大循环中的，递减到0结束，所以中途无论哪个时间+1的时刻都不会越界
- * 而位置position是小循环中限定从0到10号位置，而且定义的数组就11个0 -10 号下标那么大，
- * 求局部最优公式中需要对位置用到+1，-1，不变的三个操作，不变操作肯定是没问题的,-1,+1 则会在边界出问题。
- */
- /* position循环开始为0的时候，你去-1，他就变成-1位置了，
- */ 他走的时候0-10号没-1这个位置，而且数组索引位置为-1会发生啥我也不知道，所以这里也要判断一下
- if((position-1 >= 0) && (dp[position-1][time+1] > particalMax)) {
- particalMax = dp[position-1][time+1];
- }
- /* 而当position循环到等于10的时候进行+1，这样就会导致数组越界，而且从实际情况来说，现实中最大的位置是10号，也没有11号
- * 解决办法是有的，可以扩大一些数组position，然后扩大后的那部分无论在什么时间time都赋值为0，
- */ 我觉得这样做没必要，到界了就不理他不做操作就好了。
- if((position+1 <= 10) && dp[position+1][time+1] > particalMax) {
- particalMax = dp[position+1][time+1];
- }
- dp[position][time] = exactly[position][time] +particalMax; //公式
- }
- }
- System.out.println("0时刻站在5位置往后最多能接到饼是:"+dp[5][0]);
- }
- }
写的太啰嗦了，代码没几行，可是我写代码的时候遇到的问题就是那么多，第一次写博客，为什么没有缩进呢，这样不好看啊，罢了罢了，万事开头难，纪念一下