洛谷 P1725 怎么wa了?
代码:
```c++
#include
using namespace std;
priority_queue<int>q1, q2;
int n, R, L, ans;
int a[200010], f[200010];
int main() {
scanf("%d%d%d", &n, &L, &R);
for (int i = 0; i <= n; i++)scanf("%d", &a[i]);
for (int i = 1; i < L; i++)q2.push(a[i]);
for (int i = L; i <= n; i++) {
q1.push(f[i - L]);
if (i - R - 1 >= L)q2.push(f[i - R - 1]);
while (!q2.empty() && q1.top() == q2.top()) {
q1.pop();
q2.pop();
}
f[i] = q1.top() + a[i];
}
for (int i = n - R + 1; i <= n; i++)ans = max(ans, f[i]);
printf("%d", ans);
}
```
#include
#include
using namespace std;
#define N 200001
int dp[N],a[N],n,l,r;
int q[N][2],head=1,tail=0;
int main()
{
scanf("%d%d%d",&n,&l,&r);
if(l>r) swap(l,r);//防止l比r大
for(int i=0;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=n-l+1;i--)
{
dp[i]=a[i];
}
for(int i=n+1;i>=l;i--)
{
while(tail>=head&&dp[i]>q[tail][0]) tail--;
tail++;
q[tail][0]=dp[i];
q[tail][1]=i;
//以上为将dp[i]打入单调队列
dp[i-l]=q[head][0]+a[i-l];//更新
if(i+r==q[head][1]) head++;//弹出
}
cout<<dp[0];
}
洛谷 P1725 怎么wa了?
哈?这是???