网站设计制作的公司,杭州学校网站开发,个人与企业签订网站开发合同,南京需要做网站的公司传送门:CF
[前题提要]:自己在做这道题的时候思路完全想错方向,导致怎么做都做不出来,看了题解之后感觉数形结合的思考方式挺好的(或者这种做法挺典的),故写篇题解记录一下 题目很简单,不再解释.先不考虑 k k k,想想是一种什么情况?很显然应该是跟下图一样是一个折线图的变化.…传送门:CF
[前题提要]:自己在做这道题的时候思路完全想错方向,导致怎么做都做不出来,看了题解之后感觉数形结合的思考方式挺好的(或者这种做法挺典的),故写篇题解记录一下 题目很简单,不再解释.先不考虑 k k k,想想是一种什么情况?很显然应该是跟下图一样是一个折线图的变化. 然后是一个很简单的事实:我们选取的K一定是前缀和的某一个值,更为准确的来说,应该是一个即将减少的一个前缀和值.这个结论自己把玩一下应该是不难发现的,简单的讲一下为什么是这样.因为对于一个即将减少的值来说,我们不妨选取这个值,因为这个值肯定比即将减少的那个值大,那为啥不选这个更大的值呢.而对于中间段的数来说,那些数只是中间值,两端点必然有一个点比它更为优秀.
那么现在随便选取一个端点作为我们的K,看看原图会发生什么情况 考虑选择的K的值为红横线.不难发现原本白色的折线因为现在K的出现需要往左上进行一个平移. 继续看蓝色的圈,我们会发现原本的平移还不够,我们需要将整个部分进行再一次平移.(因为懒所以没有进一步画出).
上面这段操作很重要,是这一道题的关键.仔细品一下上面的操作,我们就会发现后面那部分的贡献其实就是后缀最大后缀和(两个前缀和差其实就是后缀和啦),也就是当前位置开始的所有的后缀和的最大值.直接讲可能有点抽象,建议仔细看看上面的图的平移操作.数形结合一下很好理解. PS:出现蓝圈的原因就是因为该后缀和更大.
那么这道题的解法也就呼之欲出了.考虑枚举每一个前缀和作为我们的K,然后计算一下贡献即可.
但是还存在一种特殊情况需要再仔细考虑一下: 对于上图的情况,我们会发现最后一段的后缀和贡献是负的,并且此时没办法进行平移.怎么解决?想一下平移的实际意义,不难发现应该令该贡献为0,也就是后缀最大值的初始值应该定义0 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt1)
#define rs (rt1|1)
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100);
}
#define maxn 1000000
#define int long long
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];int rmax[maxn],sum[maxn];
signed main() {int Tread();while(T--) {int nread();for(int i1;in;i) {a[i]read();}for(int i1;in;i) {sum[i]sum[i-1]a[i];}rmax[n]0;for(int in-1;i0;i--) {rmax[i]max(rmax[i1],sum[n]-sum[i]);}int maxxsum[n],anssum[n];for(int i0;in;i) {if(sum[i]rmax[i]maxx) {maxxsum[i]rmax[i];anssum[i];} }coutansendl;}return 0;
}
