http://47.96.116.66/problem.php?cid=3363&pid=7
题目描述
如今，一种叫做“超级跳跳跳！”的国际象棋游戏在ZSTU很受欢迎。也许你是一个好孩子，对这个游戏知之甚少，所以我现在介绍给你。
游戏可由两个或两个以上的玩家玩。它由一个棋盘和一些西洋棋棋子组成，所有西洋棋棋子都用正整数或“开始”或“结束”标记。玩家从起点开始，最后必须跳到终点。在跳跃过程中，玩家将访问路径中的西洋棋棋子，但是每个人都必须从一个棋子跳到另一个绝对更大的棋子（你可以假设起点是最小值，终点是最大值）。并且所有玩家都不能倒退。一个跳跃可以从西洋棋棋子到下一个，也可以穿过许多西洋棋棋子，甚至你可以直接从起点到达终点。当然，在这种情况下你得到零点。只有当玩家能够根据他的跳跃方案获得更高的分数时，才是赢家。请注意，您的得分来自您跳跃路径中西洋棋棋子的价值总和。您的任务是根据给定的西洋棋棋子列表输出最大值。
输入
输入包含多个测试用例。每个测试用例的描述如下：N value_1 value_2 … value_N保证N不大于1000且所有value_i都在32-int范围内。以0开头的测试用例表示输入终止，并且不处理该测试用例。
输出
对于每种情况，根据规则打印最大值，并且一行打印一个。
样例输入
3 1 3 2
4 1 2 3 4
4 3 3 2 1
0
样例输出
4
10
3
#include<bits/stdc++.h>using namespace std;int main(){int len[1001],a[1001];int n;while(cin>>n and n!=0){int i=0,ans;while(n--){cin>>a[i];ans=a[i];for(int j=0;j<i;j++)if(a[i]>a[j] and ans<len[j]+a[i]) ans=max(ans,len[j]+a[i]);len[i]=ans;i++;}ans=len[0];for(int j=0;j<i;j++)ans=max(ans,len[j]);cout<<ans<<endl;}return 0;}
