DP类型各题总结-acm.doc

《DP类型各题总结-acm.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最大连续子序列TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):11540    AcceptedSubmission(s):4856还需要输出该子序列的第一个和最后一个元素。 对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。思路：一路加 如果s

2、um变成小于0了 从当前位置重新新开始加（小于0的话就对整个段没有贡献了 而且会使整个段的和变小）#includeintmain(){   intn,i,a[10005],start,end,sum,max,sta,flag,cnt;   while(1)   {       cnt=0;       sum=0;max=-1;flag=1;        scanf("%d",&n);        if(n==0)return0;                for(i=0;i

3、"%d",&a[i]);            if(a[i]<0)cnt++;            if(a[i]==0)flag=0;        }        start=sta=end=a[0];        if((cnt==n

4、

5、cnt==n-1))        {            if(flag==0)            {printf("000");continue;}            else                if(n!=1)                {printf("0%d%d",a[0],a

6、[n-1]);continue;}                   }                for(i=0;imax)                {                        

7、max=sum;                        end=a[i];start=sta;                }            }        }        printf("%d%d%d",max,start,end);   }}Hdu1087superjumping题意：此题就是找序列中最大升序子序列的和。可跳不一定非要连续比如 132中升序序列有：｛1｝｛3｝｛2｝｛1，3｝｛1，2｝。所以最大为1+3=4； #include__int64a[1005],sum[1005];intmain(){   in

8、ti,j,n,max,ans;   while(scanf("%d",&n)&&n)   {       for(i=0;i(sum[j]+a[i])?sum[i]:(sum[j]+a[i]);//sum[j]之前已经求出来了           }    

9、       ans=ans>sum[i]?ans:sum[i];       }     printf("%d",ans);   }   return0;}CommonSubsequenceTimeLimit:2000/1000ms(Java/Other)   MemoryLimit:65536/32768K(Java/Other)TotalSubmission(s):29   AcceptedSubmission(s):16ProblemDescriptionAsubsequenceofagivensequenceisthegivensequ