HDU 1231(动态规划)

绝地灬酷狼 2022-06-06 00:57 302阅读 0赞

问题描述:

给定K个整数的序列{ N1, N2, …, NK },其任意连续子序列可表示为{ Ni, Ni+1, …,
Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,
例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和
为20。
在今年的数据结构考卷中,要求编写程序得到最大和,现在增加一个要求,即还需要输出该
子序列的第一个和最后一个元素。

Input

测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( < 10000 ),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。

Output

对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元
素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。

Sample Input

  1. 6
  2. -2 11 -4 13 -5 -2
  3. 10
  4. -10 1 2 3 4 -5 -23 3 7 -21
  5. 6
  6. 5 -8 3 2 5 0
  7. 1
  8. 10
  9. 3
  10. -1 -5 -2
  11. 3
  12. -1 0 -2
  13. 0

Sample Output

  1. 20 11 13
  2. 10 1 4
  3. 10 3 5
  4. 10 10 10
  5. 0 -1 -2
  6. 0 0 0

题目分析:刚刚接触动态规划,非常菜!看了学校另一个学姐的代码才会!

点击打开链接

代码如下:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. const int maxn=1e4+100;
  6. int sum,ans,s,e,anss,anse,a[maxn];
  7. int main()
  8. {
  9. int k;
  10. while (scanf("%d",&k)!=EOF) {
  11. if (k==0) break;
  12. for (int i=0;i<k;i++)
  13. scanf("%d",&a[i]);
  14. sum=ans=s=e=anss=anse=a[0];
  15. for (int i=1;i<k;i++) {
  16. if (sum>0) {
  17. sum+=a[i];
  18. e=a[i];
  19. }
  20. if (sum<=0) {//如果前缀和小于0,那么另起起点肯定更优
  21. sum=a[i];
  22. s=e=a[i];
  23. }
  24. if (sum>ans) {
  25. ans=sum;
  26. anss=s;
  27. anse=e;
  28. }
  29. }
  30. if (ans>=0) printf("%d %d %d\n",ans,anss,anse);
  31. else printf("%d %d %d\n",0,a[0],a[k-1]);
  32. }
  33. return 0;
  34. }

发表评论

表情:
评论列表 (有 0 条评论,302人围观)

还没有评论,来说两句吧...

相关阅读

    相关 HDU 1978(动态规划)

    问题描述 这是一个简单的生存游戏,你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下:  1.机器人一开始在棋盘的起始点并有起始点所

    相关 HDU 4540(动态规划)

    问题描述: 威威猫最近不务正业,每天沉迷于游戏“打地鼠”。    每当朋友们劝他别太着迷游戏,应该好好工作的时候,他总是说,我是威威猫,猫打老鼠就是我的工作!