HDU 1003 Max Sum DP .

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1003

题目格式有毒！！！

DP1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n[maxn],d[maxn];
int main()
{int T,N,L,R,sum,kase=0; cin>>T;while(T--){memset(d,0,sizeof(d));cin>>N;for(int i=1;i<=N;i++)scanf("%d",&n[i]);for(int i=1;i<=N;i++)d[i]=max(d[i-1]+n[i],n[i]);R=max_element(d+1,d+1+N)-d;for(int i=R,sum=d[R]-n[R];i>=1;--i,sum-=n[i]) if(sum==0) L=i;printf("Case %d:\n",++kase);printf("%d %d %d\n",d[R],L,R);if(T) cout<<endl;}return 0;
}

DP2

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n[maxn],d[maxn];
int main()
{int T,N,L,R,kase=0; cin>>T;while(T--){memset(d,0,sizeof(d));cin>>N;for(int i=1;i<=N;i++)scanf("%d",&n[i]);int l,r,ans=-INF;L=R=l=r=1; d[1]=n[1];for(int i=1;i<=N;i++){if(d[i-1]+n[i]>=n[i]){d[i]=d[i-1]+n[i];r=i;                }else {d[i]=n[i];r=l=i;}if(ans<d[i]){ans=d[i];L=l;R=r;}}printf("Case %d:\n%d %d %d\n",++kase,ans,L,R);if(T) cout<<endl;}return 0;
}