1:线段树解法 对于每一个i求出最大的(i-k)区间内的sum值及id
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<sstream> #include<string> #include<climits> #include<stack> #include<set> #include<bitset> #include<cmath> #include<deque> #include<map> #include<queue> #define iinf 0x7f7f7f7f #define linf 1000000000000000000LL #define dinf 1e200 #define eps 1e-11 #define all(v) (v).begin(),(v).end() #define sz(x) x.size() #define pb push_back #define mp make_pair #define lng long long #define sqr(a) ((a)*(a)) #define pii pair<int,int> #define pll pair<lng,lng> #define pss pair<string,string> #define pdd pair<double,double> #define X first #define Y second #define pi 3.14159265359 #define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i) #define ffd(i,xi,n) for(int i=xi;i>=(int)(n);--i) #define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next) #define cc(i,j) memset(i,j,sizeof(i)) #define two(x) ((lng)1<<(x)) #define lson l , mid , rt << 1 #define rson mid + 1 , r , rt << 1 | 1 #define mod 1000000007 #define pmod(x,y) (x%y+y)%y using namespace std; typedef vector<int> vi; typedef vector<string> vs; template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;} template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;} template<class T> inline T Min(T x,T y){return (x>y?y:x);} template<class T> inline T Max(T x,T y){return (x<y?y:x);} template<class T> T Abs(T a){return a>0?a:(-a);} template<class T> inline T lowbit(T n){return (n^(n-1))&n;} template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));} int k,a[11111],sum[11111],s[44444]; void push_up(int rt) { if(sum[s[rt<<1]]>=sum[s[rt<<1|1]]) s[rt]=s[rt<<1]; else s[rt]=s[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r) { s[rt]=l; return ; } int mid=(l+r)>>1; build(lson); build(rson); push_up(rt); } int query(int L,int R,int l,int r,int rt) { if(l>=L&&R>=r) { return s[rt]; } int ret=-iinf; int mid=(l+r)>>1; if(L<=mid) { ret=query(L,R,lson); } if(R>mid) { int y; if(ret==-iinf) ret=query(L,R,rson); else if(sum[ret]<sum[y=query(L,R,rson)]) ret=y; } return ret; } int main() { while(scanf("%d",&k)==1) { if(k==0) break; ff(i,1,k) scanf("%d",a+i); sum[0]=0; ff(i,1,k) sum[i]=sum[i-1]+a[i]; int ans1=-iinf,le,ri; build(1,k,1); ff(i,1,k) { int r; int u=sum[r=query(i,k,1,k,1)]-sum[i-1]; // cout<<u<<" "<<r<<endl; if(u>ans1) ans1=u,le=i,ri=r; // cout<<ans1<<" "<<le<<" "<<ri<<endl; } if(ans1<0) ans1=0,le=1,ri=k; printf("%d %d %d\n",ans1,a[le],a[ri]); } return 0; }
2: YY解法 贪心
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<sstream> #include<string> #include<climits> #include<stack> #include<set> #include<bitset> #include<cmath> #include<deque> #include<map> #include<queue> #define iinf 0x7f7f7f7f #define linf 1000000000000000000LL #define dinf 1e200 #define eps 1e-11 #define all(v) (v).begin(),(v).end() #define sz(x) x.size() #define pb push_back #define mp make_pair #define lng long long #define sqr(a) ((a)*(a)) #define pii pair<int,int> #define pll pair<lng,lng> #define pss pair<string,string> #define pdd pair<double,double> #define X first #define Y second #define pi 3.14159265359 #define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i) #define ffd(i,xi,n) for(int i=xi;i>=(int)(n);--i) #define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next) #define cc(i,j) memset(i,j,sizeof(i)) #define two(x) ((lng)1<<(x)) #define lson l , mid , rt << 1 #define rson mid + 1 , r , rt << 1 | 1 #define mod 1000000007 #define pmod(x,y) (x%y+y)%y using namespace std; typedef vector<int> vi; typedef vector<string> vs; template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;} template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;} template<class T> inline T Min(T x,T y){return (x>y?y:x);} template<class T> inline T Max(T x,T y){return (x<y?y:x);} template<class T> T Abs(T a){return a>0?a:(-a);} template<class T> inline T lowbit(T n){return (n^(n-1))&n;} template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));} int k,a[11111]; int main() { while(scanf("%d",&k)==1) { if(k==0) break; ff(i,1,k) scanf("%d",a+i); int sum=0; int l=1,r,ans=-iinf,le,ri; ff(i,1,k) { if(sum+a[i]<0) { sum+=a[i]; if(ans<sum) ans=sum,le=l,ri=r; sum=0; l=i+1; } else { r=i; sum+=a[i]; if(ans<sum) ans=sum,le=l,ri=r; } } if(ans<0) ans=0,le=1,ri=k; printf("%d %d %d\n",ans,a[le],a[ri]); } return 0; }
3:dp解法
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<sstream> #include<string> #include<climits> #include<stack> #include<set> #include<bitset> #include<cmath> #include<deque> #include<map> #include<queue> #define iinf 0x7f7f7f7f #define linf 1000000000000000000LL #define dinf 1e200 #define eps 1e-11 #define all(v) (v).begin(),(v).end() #define sz(x) x.size() #define pb push_back #define mp make_pair #define lng long long #define sqr(a) ((a)*(a)) #define pii pair<int,int> #define pll pair<lng,lng> #define pss pair<string,string> #define pdd pair<double,double> #define X first #define Y second #define pi 3.14159265359 #define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i) #define ffd(i,xi,n) for(int i=xi;i>=(int)(n);--i) #define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next) #define cc(i,j) memset(i,j,sizeof(i)) #define two(x) ((lng)1<<(x)) #define lson l , mid , rt << 1 #define rson mid + 1 , r , rt << 1 | 1 #define mod 1000000007 #define pmod(x,y) (x%y+y)%y using namespace std; typedef vector<int> vi; typedef vector<string> vs; template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;} template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;} template<class T> inline T Min(T x,T y){return (x>y?y:x);} template<class T> inline T Max(T x,T y){return (x<y?y:x);} template<class T> T Abs(T a){return a>0?a:(-a);} template<class T> inline T lowbit(T n){return (n^(n-1))&n;} template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));} int dp[11111],k,le[11111],a[11111]; int main() { while(scanf("%d",&k)==1) { if(!k) break; ff(i,1,k) scanf("%d",a+i); dp[0]=-iinf; ff(i,1,k) if(dp[i-1]+a[i]<a[i]) dp[i]=a[i],le[i]=i; else dp[i]=dp[i-1]+a[i],le[i]=le[i-1]; int ans=-iinf,l,r; ff(i,1,k) if(ans<dp[i]) ans=dp[i],l=le[i],r=i; if(ans<0) ans=0,l=1,r=k; printf("%d %d %d\n",ans,a[l],a[r]); } return 0; }
总的来看: yy思路以及线段树思路来的比较容易 (当然st算法也可以做·我就不写了)