Pro 在一年前赢得了小镇的最佳草坪比赛后,tw 变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,tw 希望能够再次夺冠。 然而,tw 的草坪非常脏乱,因此,tw 只能够让他的奶牛来完成这项工作。tw 有 N(1 <= N <= 100,000)只排成一排的奶牛,编号为 1...N。每只奶牛的效率是不同的,奶牛 i 的效率为 E_i(0 <= E_i <= 1,000,000,000)。 靠近的奶牛们很熟悉,因此,如果 tw 安排超过 K 只连续的奶牛,那么,这些奶牛就会罢工去开派对:)。因此,现在 tw 需要你的帮助,计算 tw 可以得到的最大效率,并且该方案中没有连续的超过 K 只奶牛。
Input 第一行:空格隔开的两个整数 N 和 K 第二到 N+1 行:第 i+1 行有一个整数 E_iOutput 一个值,表示 tw 可以得到的最大的效率值。
Sample Input 5 2 1 2 3 4 5Sample Output 12
Data Range 30% 的数据, n<=100 100% 的数据, n<=100000
随便说说版：
刚刚才弄懂题目是什么意思qwq
看来还是没有融会贯通"要揣测出题人的意图"这句话
或者说我语文太差了(这确实是一个事实)
正解：
f[i] 表示安排前 i 个奶牛所获得的最大值
若i>k 那么 i-k ~ i 中至少有一个不选
不选的点为 j 即为断点
然后进入DP常规套路 枚举阶段 枚举断点 转移
但是
这样子会超时 开O2也超时qwq 我们不得不想想优化
单调队列优化：
发现我们枚举断点就是为了求出 f[j-1]-s[j] 的最大值
而 j 是一格一格往右移的 所以想到了 然后 没了
这里再讲一下滑动窗口：
q[i]: 是单调队列 p[i]:是单调队列中 i 号元素在原来序列里的下标
当要加入一个新的元素 y 的时候 先使队尾比 y 小的元素出队( tail-- )
因为这些元素在有生之年已经没有机会成为最大的了
（单调队列中的元素要成为最大元素，只有当比它大的元素都退休(滑出了窗口外)才行，现在来了一个比它大还比它年轻的元素，它自然没机会了）
y 入队
然后把滑出窗口外的元素弹出( head++ ) p 数组就是用于这一步
就可以啦
1 #include2 #include 3 #define ll long long 4 #define go(i,a,b) for(register int i=a;i<=b;i++) 5 using namespace std; 6 int read() //cannot read "-" 7 { 8 int x=0;char c=getchar(); 9 while(c<'0'||c>'9') c=getchar();10 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}11 return x;12 }13 ll n,k,a[100010],s[100010],dp[100010];14 int main()15 {16 n=read();k=read();17 go(i,1,n) a[i]=read(),s[i]=s[i-1]+a[i];18 dp[1]=a[1];19 go(i,1,n)20 {21 if(i>k)22 {23 go(j,i-k,i) dp[i]=max(dp[i],dp[j-1]+s[i]-s[j]);24 }25 else dp[i]=s[i];26 }27 printf("%lld",dp[n]);28 return 0;29 }
1 #include2 #include 3 #define ll long long 4 #define go(i,a,b) for(register int i=a;i<=b;i++) 5 using namespace std; 6 int read() //cannot read "-" 7 { 8 int x=0;char c=getchar(); 9 while(c<'0'||c>'9') c=getchar();10 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}11 return x;12 }13 ll n,k,head=1,tail=1,a[100010],s[100010],f[100010],q[100010*2],p[100010*2];14 ll find(int x) //这里是单调队列优化 ! ! !15 {16 ll y=f[x-1]-s[x];17 while(head<=tail&&q[tail]<=y) tail--;18 q[++tail]=y; p[tail]=x;19 while(p[head]