Running_a_way @ 2023-10-13 14:23:08
检查一下单调队列弹出队首的边界有没有写错，参考下列代码：
for (int i = l; i <= n; i++) {
while(q.size() && dp[q.back()] <= dp[i - l]) q.pop_back();
while(q.size() && (i - l) - q.front() > (r - l)) q.pop_front(); // AC
q.push_back(i - l);
dp[i] = dp[q.front()] + a[i];
if(i + r > n) ans = max(ans, dp[i]);
}for (int i = l; i <= n; i++) {
while(q.size() && dp[q.back()] <= dp[i - l]) q.pop_back();
while(q.size() && (i - l) - q.front() > (r - l + 1)) q.pop_front(); // WA on HACK
q.push_back(i - l);
dp[i] = dp[q.front()] + a[i];
if(i + r > n) ans = max(ans, dp[i]);
}不得不说 hack 真挺强的。
by lonely_cyx @ 2023-10-13 14:31:46
这题好像n^2就能过......
by Special_Tony @ 2023-10-13 14:36:20
@lonely_cyx 啊？那就有必要修修了
by lovely_hyzhuo @ 2023-10-13 15:13:16
@sz_mane 代码
A了
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1000010];
int n,l,r;
int a[1000010];
signed main()
{
cin>>n>>l>>r;
for(int i=0;i<=n;i++)
{
cin>>a[i];
dp[i]=-0x3f3f3f3f;
}
dp[0]=a[0];
for(int i=1;i<n+l;i++)
{
for(int j=l;j<=min(r,i);j++)
dp[i]=max(dp[i],dp[i-j]+a[i]);
}
int ans=-0x3f3f3f3f;
for(int i=n;i<n+l;i++)
{
if(dp[i]!=0)
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}by Special_Tony @ 2023-10-13 15:16:04
@lonely_cyx 啊？代码？提交记录？
by lovely_hyzhuo @ 2023-10-13 15:16:55
@sz_mane https://www.luogu.com.cn/record/119523538
by lovely_hyzhuo @ 2023-10-13 15:17:27
@sz_mane 快的飞起
by Special_Tony @ 2023-10-13 15:18:41
《622ms》卡常？
by Special_Tony @ 2023-10-13 15:18:48
我去Hack
by lovely_hyzhuo @ 2023-10-13 15:23:02
@sz_mane 我就正常用的cin,cout,流同步都没关
by Special_Tony @ 2023-10-13 15:26:41
Hack.in生成器：
# include <bits/stdc++.h>
using namespace std;
int main () {
cout << "200000 0 200000\n";
for (int i = 0; i <= 200000; ++ i)
cout << "0 ";
return 0;
}Hack.out
0所以请@RSY 添Hack