前缀和
计算二位前缀和，再利用容斥原理计算出答案即可。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=5000+10; 7 int n, r, sum[maxn][maxn]; 8 9 int main() {10 scanf("%d%d", &n, &r);11 int x, y, v, maxx=0, maxy=0;12 maxx=maxy=r;13 for (int i=1; i<=n; ++i) {14 scanf("%d%d%d", &x, &y, &v);15 ++x; ++y;16 maxx=max(maxx, x); maxy=max(maxy, y);17 sum[x][y]=v;18 }19 for (int i=1; i<=maxx; ++i) {20 for (int j=1; j<=maxy; ++j) {21 sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];22 }23 }24 //枚举面积为r的正方形25 int ans=0;26 for (int i=r; i<=maxx; ++i) {27 for (int j=r; j<=maxy; ++j) {28 ans=max(ans, sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);29 }30 } 31 printf("%d\n", ans);32 return 0;33 }
差分
求出序列a的差分序列b，令bn+1=0，目标是将把b2,b3...bn变为全0。
把序列a区间[l,r]加d，其差分序列的变化为Bl加d,Br+1减d。
从b1,b2...bn中任选两个数的方法可以分为4类：
1.选bi和bj
2.选b1和bj
3.选bi和bn+1
4.选b1和bn+1,这种选法没有意义
设整数总和为p，负数总和为q，首先以正负数匹配的方式尽量选择操作1，可执行min(p,q)次。
剩余|p-q|个未配对，执行操作2和操作3，共需|p-q|次。
所以最少操作次数为min(p,q)+|p-q|=max(p,q)次，根据操作2,3的选择情况，能产生|p-q|+1种b1的值，即序列a可能有|p-q|+1种。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn=100000+10; 8 long long n, a[maxn], s[maxn], p=0, q=0; 9 10 int main() {11 scanf("%lld", &n);12 for (int i=1; i<=n; ++i)13 scanf("%lld", &a[i]);14 s[1]=a[1]; s[n+1]=0;15 for (int i=2; i<=n; ++i) {16 s[i]=a[i]-a[i-1];17 }18 for (int i=2; i<=n; ++i) {19 if (s[i]>0) p+=s[i];20 else if (s[i]<0) q-=s[i];21 }22 printf("%lld\n%lld\n", max(p,q), abs(p-q)+1);23 return 0;24 }
若有一条关系指明Ai和Bi可以互相看见，就将他们数组中Ai+1到Bi-1的数减去1，最终得到所有牛与最高的牛p的相对身高关系。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include