hdu 1087 Super Jumping! Jumping! Jumping!(动态规划)

hdu 1087 Super Jumping! Jumping! Jumping!(动态规划)

题意:

  求解最大递增子序列。

  例如:3 1 3 2

  输入 3  个数 1 3 2

  则递增子序列有 {1} {3} {2} {1 3} {1 2} ,故输出子序列的最大和 4

解题思路:

  x[n](n个数) 数组存储 输入的数据

  dp[i] 用来记录 前 i+1 {数据从下标为0开始存储}个数的 最大结果

  遍历dp[] 找到最大值即可。

因 G20 网站暂停提交

明天测试代码。

2016.08.27 代码提交成功!

代码如下:

 #include<bits/stdc++.h>
using namespace std;
int x[];
int dp[];
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int i,j,maxx=;
for(i=; i<n; i++)
{
scanf("%d",&x[i]);
}
memset(dp,,sizeof(dp));
dp[]=x[];
for(i=; i<n; i++)
{
for(j=; j<i; j++)
{
if(x[i]>x[j])
dp[i]=max(dp[j],dp[j]+x[i]);
}
dp[i]=max(dp[i],x[i]);
maxx=max(dp[i],maxx);
}
printf("%d\n",maxx);
}
return ;
}
上一篇:HDU 1018 大数(求N!的位数/相加)


下一篇:angularjs学习总结一(表达式、指令、模型)