题目描述
小Biu去逛超市，超市有一个长度为n的货架，第i个位置摆放着价值为a[i]的商品，小Biu有很多好朋友，他想给好朋友们买一些礼物，但是小Biu又是一个很细心地人，他想让所有朋友收到的礼物的总和一样，而且送给每个朋友的礼物必须是位置连续的一段商品，小Biu想知道他最多可以给多少个好朋友送出礼物。
输入
第一行两个整数n(1<=n<=1000)。
第二行n个整数,第i个整数为第i个数字a[i],(1<=a[i]<=20)。
输出
输出一个数字表示答案。
样例输入
5 1 3 4 3 1
样例输出
3
提示
样例解释：[1,3] [4] [3,1] 可以分为三个不相交而且区间和相等的区间。
20%的数据中，1<=n<=10
50%的数据中，1<=n<=100
100%的数据中，1<=n<=1000
这个提示贪心的思想，求可能分成相等的区间和的段数
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} ///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) ///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 int n,a[1008]; int ans; map<int,int>cnt; map<int,int>righ; start { n=read; for(int i=1;i<=n;i++){ int temp=read; a[i]=a[i-1]+temp; for(int j=i-1;j>=0;j--){ int val=a[i]-a[j]; if(righ[val]<=j){ cnt[val]++; righ[val]=i; ans=max(ans,cnt[val]); } } } cout<<ans; end; }
