**题目,出题人说的什么G2玩意
还是有收获的
目前的斜率dp问题大致分为两类
1.总结公式后,进行线性规划求解
2.数形结合,与凸包相似。
本题属于第二种。
我们可以求一个前缀和。
然后我们可以知到,对于目前的节点j
其实就是在0->j-k中找一个点,使得(sum[j]-sum[i])/(j-i)最大。
我们如果硬是用dp的话,那么就是n^2级。
很明显这个形式让我们想到了斜率优化。
首先我们维护的是一个下凸包。
为什么是这样的呢?建议看这篇博客的分析,他对斜率dp的凸包分析方法,我觉得十分有用,精辟!!!!
那么我们就维护下凸包就行了。
关键的第二弹:
如何在O(1)的时间内得到答案?
在上面的博客中,他说可以通过斜率的比较pop前面的点。因为他们一定不是后面dp的答案。
但是我认为这是错的。其实还是有可能是后面的最有答案的,
但是一定不会是全局的最优答案了。所以被我们pop掉了。
#include<iostream> #include<algorithm> using namespace std; const int max_n = 1e5+100; //输入外挂 int tottt; const int BUF=25000000; char Buf[BUF],*buf=Buf; inline void read(int &a){ for(a=0;*buf<48;buf++); while(*buf>47) a=a*10+*buf++-48; } int a[max_n]; int n,k; int que[max_n<<1]; int ql,qr; double geth(int x1,int x2){ return (1.0*a[x1]-1.0*a[x2])/(1.0*x1-1.0*x2); } int main(){ tottt=fread(Buf,1,BUF,stdin); while (1){ if(buf-Buf+1>=tottt)break; read(n);read(k); ql=qr=1; for (int i=1;i<=n;++i)read(a[i]); for (int i=1;i<=n;++i)a[i]+=a[i-1]; double ans = 1.0*a[k]/1.0*k; que[qr++]=0; for (int i=k+1;i<=n;++i){ int p = i-k;int pn = i; while (qr-ql>=2&&geth(que[qr-2],que[qr-1])>=geth(que[qr-1],p))--qr; que[qr++]=p; while (qr-ql>=2&&geth(que[ql],que[ql+1])<=geth(que[ql+1],pn))++ql; ans = max(ans,geth(que[ql],pn)); }printf("%.2lf\n",ans); } }
顺便收获了一个输入外挂