拨云见日 @ 2019-10-23 10:31:52
ll head=0,tail=1;过了
ll head=1,tail=0;20分by 拨云见日 @ 2019-10-23 10:37:28
甚至两个都为一也可以过
by 爷，无限霸气 @ 2019-10-23 10:42:23
上次不是那个并查集乱改都AK吗？
by Bbaka @ 2019-10-23 11:40:49
那要看你的队列是怎么写的呀..
by Bbaka @ 2019-10-23 11:41:28
如果入队的时候是tail++那么第二种写法肯定有问题
by Bbaka @ 2019-10-23 11:41:31
@拨云见日
by 拨云见日 @ 2019-10-23 11:47:06
@IQZ_
#include<bits/stdc++.h>
#define ll long long
const ll maxn = 100005;
ll q[maxn];
ll a[maxn], sum[maxn];
ll n, k;
ll dp[maxn][2];
ll maxx(ll a,ll b)
{
if(a>=b) return a;
else return b;
}
ll head=0,tail=1;
int main()
{
scanf("%lld %lld", &n, &k);
for(ll i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
for(int i=1;i<=n;i++)
{
dp[i][0]=maxx(dp[i-1][0],dp[i-1][1]);
while(head<=tail&&q[head]<i-k) head++;
dp[i][1]=dp[q[head]][0]+sum[i]-sum[q[head]];
while(sum[i]-dp[i][0]<sum[q[tail]]-dp[q[tail]][0]) tail--;
q[++tail]=i;
}
printf("%lld\n", maxx(dp[n][0],dp[n][1]));
}by Bbaka @ 2019-10-23 12:09:39
@拨云见日 你可以手动模拟一下你的入队过程你就知道为什么会有问题了
by Bbaka @ 2019-10-23 12:09:51
@拨云见日 指的是你的第二种写法