【CF1141F2】Same Sum Blocks

题解：发现可以通过枚举区间将区间和相同的元组记录在一个表中，对于答案来说，在同一个表中的元组的选择才会对答案产生贡献。发现每一个表中都是一个个区间，问题转化成了对于每一个表来说，选择若干个不相交的区间，使得选择出来的区间数量最多，直接贪心即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int maxn=1501;

int n,a[maxn],sum[maxn],ans;
map<int,vector<P>> mp;
vector<P> rec;

bool cmp(P a,P b){return a.second<b.second;}

void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			mp[sum[j]-sum[i-1]].push_back(make_pair(i,j));
	auto p=mp.begin();
	for(;p!=mp.end();p++){
		vector<P> &res=p->second;
		sort(res.begin(),res.end(),cmp);
		int cnt=0,last=-1;
		vector<P> tmp;
		for(int i=0;i<res.size();i++)
			if(res[i].first>last){
				++cnt,last=res[i].second;
				tmp.push_back(res[i]);
			}
		if(ans<cnt)ans=cnt,rec=tmp;
	}
	printf("%d
",ans);
	for(int i=0;i<rec.size();i++)printf("%d %d
",rec[i].first,rec[i].second);
}

int main(){
	solve();
	return 0;
}