hdu1087Super Jumping! Jumping! Jumping!(最大递加序列和)

hdu1087Super Jumping! Jumping! Jumping!(最大递增序列和)

题意：棋牌游戏如今，一种被称为“超级跳！跳！跳！“HDU是非常流行的。也许你是个好孩子，这个游戏知之甚少，所以我介绍给你吧。

可以玩游戏由两个或两个以上的球员 ??。它由一个棋盘（棋盘）和一些棋子（棋子），所有的棋子标记的正整数或“开始”或“结束”。玩家从起始点和终点终于跳进。在跳跃的过程中，玩家将访问路径中的棋子，但每个人都必须从一个棋子跳跃到另一个绝对更大（可以假定启动点是一个最小和终点是一个最大）。所有玩家都可以不走回头路。一个跳跃到下一个棋子，也可以去跨越许多的棋子，甚至你可以从起始点到终点直线。当然，在这种情况下，你得到零点。一个球员是一个胜利者，当且仅当，他可以根据他跳的解决方案，获得更大的成绩。请注意，你的分数来自你跳路径上的棋子价值的总和，
你的任务是输出的最大值，根据给定的棋子列表。

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1087

题目解析：简单的来说就是求一个序列中一组递增序列的最大和；

如：1，9，6 ，2 ，4，10，5，3，2

它的最大递增序列和为20，递增序列为1，9，10

和最大递增序列有点相似，但算法不太相同；

运行时间：

9139511 Accepted108715MS432K856 BC++
代码实现：

#include<stdio.h>#include<cstring>using namespace std;#pragma comment(linker,"/STACK:102400000,102400000")#define MAX  1005int dp[MAX];//dp[i]存储与num[i]构成递增序列中和最大的一个；int num[MAX];int max(int a,int b){     return(a>b?a:b);}int main(){  //freopen("input.txt","r",stdin);     int i,j,n;     while(scanf("%d",&n),n)     {          for(i=0;i<n;i++)          scanf("%d",&num[i]);          dp[0]=num[0];          int max1=0;          for(i=1;i<n;i++)          {               dp[i]=num[i];               for(j=0;j<i;j++)               {                    if(num[i]>num[j])//找出比num[i]小的数num[j]，dp[j]存储与num[j]构成递增序列中和最大的一个；所以加上num[i],也构成递增序列，                    {                         if(dp[i]<dp[j]+num[i])//比较与num[i]能构成递增序列的这些序列和，找出最大的一个，                         dp[i]=dp[j]+num[i];                    }               }               max1=max(dp[i],max1);//max1为这些递增序列中和最大的一个；          }          printf("%d\n",max1);     }   return 0;}

查看更多 下一篇