HDOJ 1087 （JAVA实现 最大上升子序列和dp）

Super Jumping! Jumping! Jumping!

原题链接 HDOJ1087

Problem Description Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.

在这里插入图片描述

The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path. Your task is to output the maximum value according to the given chessmen list.

Input Input contains multiple test cases. Each test case is described in a line as follow: N value_1 value_2 …value_N It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int. A test case starting with 0 terminates the input and this test case is not to be processed.

Output For each case, print the maximum according to rules, and one line one case.

Sample Input 3 1 3 2 4 1 2 3 4 4 3 3 2 1 0

Sample Output 4 10 3

开始做动态规划类型题了，看到这道题的第一想法我是用贪心，结果自然是WA了，贪心得到的不一定是最优解，比如1 9 5 7 8，使用贪心算法求得的值是10，但实际上最大值是1+5+7+8。所以这是一道求最长上升子序列和的问题，但是！！！一个很重要的问题，我不会实现?，想了很久，还是没找到状态方程，看了题解，是从后往前开始枚举，但我是从前往后，这就将问题变得更复杂了，所以就没有解决。但自己经过两个多小时的思考，已经初步锻炼了dp的思想，还得需要多做题来掌握掌握。

进入正题：

我们可以从后向前枚举，设dp[i]是以第i个数为结尾，那么你所需要做的就是对棋盘每个格子的价值，从0枚举到i-1，挑选其中小于dp[i]的值，核心代码如下：

			dp[0]=arr[0];
			for(int i=1;i<t;i++) {
				dp[i]=arr[i];
				for(int j=0;j<i;j++) {
					if(arr[j]<arr[i]) {
						dp[i]=Math.max(dp[i],dp[j]+arr[i]);
					}
				}
			}

最后再对dp数组的值进行遍历，找出其中最大的值。

AC代码如下

import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner cin=new Scanner(System.in);
		while(true) {
			int t=cin.nextInt();
			if(t==0) break;
			int[] arr=new int[t];
			int[] dp=new int[t];
			for(int i=0;i<t;i++) {
				arr[i]=cin.nextInt();
			}
			long ans=-1;
			dp[0]=arr[0];
			for(int i=1;i<t;i++) {
				dp[i]=arr[i];
				for(int j=0;j<i;j++) {
					if(arr[j]<arr[i]) {
						dp[i]=Math.max(dp[i],dp[j]+arr[i]);
					}
				}
			}
			for(int i=0;i<t;i++) {
				ans=Math.max(ans, dp[i]);
			}
			System.out.println(ans);
		}
	}
}