DP类型各题总结-acm.docVIP

? 最大连续子序列 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11540????Accepted Submission(s): 4856 还需要输出该子序列的第一个和最后一个元素。 ?对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 思路：一路加? 如果sum变成小于0了? 从当前位置重新新开始加（小于0的话 就对整个段没有贡献了? 而且会使整个段的和变小） #includestdio.hint main(){??? int n,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) return 0;???????? ???????? for(i=0;in;i++)???????? {???????????? scanf(%d,a[i]);???????????? if(a[i]0) cnt++;???????????? if(a[i]==0) flag=0;???????? }???????? start=sta=end=a[0];???????? if((cnt==n||cnt==n-1))???????? {???????????? if(flag==0)???????????? {printf(0 0 0\n); continue;}???????????? else ???????????????? if(n!=1)???????????????? { printf(0 %d %d\n,a[0],a[n-1]);continue;}??????????? ???????? }???????? ???????? for(i=0;in;i++)???????? {???????????? sum=sum+a[i];???????????? if(sum0i+1n)???????????? {???????????????? sta=a[i+1]; sum=0;???????????? }???????????? else ???????????? {???????????????? if(summax)???????????????? {???????????????????????? max=sum;???????????????????????? end=a[i];start=sta;???????????????? }???????????? }???????? }???????? printf(%d %d %d\n,max,start,end);??? }} Hdu 1087 super jumping ?题意：此题就是找序列中最大升序子序列的和。 可跳 不一定非要连续 比如 ?1 3 2 中升序序列有：｛1｝｛3｝｛2｝｛1，3｝｛1，2｝。所以最大为1+3=4； ? #includestdio.h__int64 a[1005],sum[1005];int main(){??? int i,j,n,max,ans;??? while(scanf(%d,n)n)??? {??????? for(i=0;in;i++) {scanf(%I64d,a[i]);sum[i]=a[i];}??????? ans=0;??????? for(i=0;in;i++)//j比i小 ??????? {??????????? for(j=0;ji;j++)??????????? { if(a[j]a[i]) sum[i]=sum[i](sum[j]+a[i])?sum[i]:(sum[j]+a[i]);//sum[j] 之前已经求出来了 ??????????? }??????????? ans=anssum[i]?ans:sum[i];??????? }????? printf(%d\n,ans);??? }??? return 0;} ? Common Subsequence Time Limit : 200