题目大意 ： 给你最多不超过1500个整数，求出最多的不相交的区间，使得每个区间和都是一样的。输出方案，任意方案都可以了。

 

思路： 我们可以把每个区间和都计算出来，然后放到相应的位置。 

 

对于区间和相同的区间，我们从左到右做一次贪心寻找最多可以留下的不相交的区间。 

1 #include
      
        2 using namespace std;   3 #define R register int  4 #define rep(i,a,b) for(R i=a;i<=b;i++)  5 #define Rep(i,a,b) for(R i=a;i<=b;i--)   6 #define ms(i,a)    memset(a,i,sizeof(a))   7 #define gc()       getchar()    8 #define pii        pair
       
           9 #define mp         make_pair10 template
        
         void read(T &x){11     x=0; char c=gc(); int w=0;  12     while (!isdigit(c))  w+=c=='-',c=gc(); 13     while(isdigit(c)) x=x*10+(c^48),c=gc();  14     if(w) x=-x;  15 }16 int const N=1500+3;  17 map
         
          
            > mat;  18 map
           
            
              > :: iterator p; 19 vector
             
               now,best,tmp; 20 int n,a[N],ans; 21 int main(){22 read(n); 23 rep(i,1,n) read(a[i]); 24 rep(i,1,n){25 int sum=0; 26 rep(j,i,n){27 sum+=a[j]; 28 mat[sum].push_back(mp(i,j)); 29 }30 }31 for(p=mat.begin();p!=mat.end();p++){32 tmp=p->second; 33 int r=0,num=0; 34 now.clear(); 35 for(int i=0;i
              
               tmp[i].second){37 r=tmp[i].second; 38 now.pop_back(); 39 now.push_back(tmp[i]); 40 }41 else if(tmp[i].first>r) {42 r=tmp[i].second; 43 num++; 44 now.push_back(tmp[i]); 45 }46 } 47 if(now.size()>ans){48 best=now; 49 ans=now.size(); 50 }51 }52 53 printf("%d\n",ans); 54 for(int i=0;i