题意：给一个长度为n的数组，在这个数组中找出一些不相邻且不相交的区间，使得区间和相等，最多能找到多少这样的区间，输出区间个数和区间左右边界。
两道题同样的题面，改变了n值的大小，1500的长度其实也不是很大，支持N^2暴力，因此我们直接暴力计算出所有1500×1500个区间和，有了区间以及区间和，就可以从中根据某个和相等的情况下得到尽量多的不相邻相交区间。
对于某个确定的区间和，有多个可能相交的区间，这些区间用贪心的方法排个序，取右边界最小的区间，即可得到最多数量的相同数量和区间。
对于每个区间和这样计算出并存储出尽量多的不相邻不相交区间。在这个过程中一直取一个区间数量的最大值，最后输出该最大值所有区间即可。
整个过程分为3步:
①计算所有区间和，并分类存储所有区间
②排序区间和，贪心处理出每个区间和的最大不相邻不相交区间数量
③根据第二步中维护的最大区间数量，得到相应结果的区间和，并直接输出筛选到的区间边界
所用时间1153Ms，内存158000 KB
代码如下：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1507;
int n;
LL a[maxn];
struct node
{
int l,r;
LL sum;
node() {}
node(int a,int b,LL c)
{l=a,r=b,sum=c;}
bool operator <(const node &a)const
{return r<a.r;}
};
map<LL,vector<node> >mp,ans;
map<LL,vector<node> >::iterator it;
LL ss[maxn];
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
ss[i]=a[i]+ss[i-1];
}
for(int i=1; i<=n; i++)
{
for(int l=0,r=l+i; r<=n; l++,r++)
{
LL tmp=ss[r]-ss[l];
mp[tmp].push_back(node(l+1,r,tmp));
}
}
LL ansval=0,cnt=0;
for(it=mp.begin(); it!=mp.end(); it++)
{
sort(it->second.begin(),it->second.end());
int tmp=0,tim=0;
for(int i=0; i< it->second.size(); i++)
{
if(it->second[i].l>tim)
{
ans[it->first].push_back(it->second[i]);
tmp++,tim=it->second[i].r;
}
}
if(tmp>cnt)cnt=tmp,ansval=it->first;
}
printf("%d
",cnt);
for(int i=0; i<cnt; i++)
printf("%d %d
",ans[ansval][i].l,ans[ansval][i].r);
}