HDU1087超级跳跃~跳~跳~(DP)

题目

如今，一种名为“超级跳跃！跳！跳！” 在HDU中非常受欢迎。也许您是个好孩子，对这个游戏了解得很少，所以现在向您介绍一下。

该游戏可以由两个或两个以上的玩家玩。它由一个棋盘（棋盘）和一些棋子（棋子）组成，所有棋子均标有正整数或“开始”或“结束”。播放器从起点开始，必须最终跳到终点。在跳跃过程中，玩家将走访这条棋子，但每个人都必须从一个棋子跳到另一个绝对更大的棋子（您可以假设起点是最小值，终点是最大值）。而且所有玩家都不能后退。一跳可以从一个国际象棋棋子跳到下一个，也可以跨越许多国际象棋棋子，甚至您也可以从起点直接到达终点。在这种情况下，您当然会得到零分。一个球员只有并且根据他的跳跃解决方案能够获得更大的分数时才是赢家。
您的任务是根据给定的西洋棋棋子列表输出最大值。

输入格式

输入包含多个测试用例。每个测试用例的描述如下：N n[1]、n[2]、n[3]….n[N]确保N不超过1000，并且所有n[i]都在32-int范围内。以0开头的测试用例将终止输入，并且该测试用例将不被处理。

输出格式

对于每种情况，请按照规则打印最大值，然后一行打印一种情况。

样例输入

样例输出

1
2
3

4
10
3

代码

#include<bits/stdc++.h>
using namespace std;
int dp[1010];//第一个存时间，第二个存位置 
int a[1010];
const int inf=0x7fffffff;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF&&n){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            int num=-111111111;
            for(int j=0;j<i;j++){
                if(a[i]>a[j]){        //判断是否能跳 
                    num=max(num,dp[j]);//判断他的前面和取最大 
                }
            }
            dp[i]=num+a[i];//最优+本身 
        }
        int sum=-1111111;
        for(int i=0;i<=n;i++){
            sum=max(sum,dp[i]);
        }
        printf("%d\n",sum);
    } 
    return 0;
}