【解题报告】洛谷P1725 琪露诺
题目链接
https://www.luogu.com.cn/problem/P1725
思路
这道题目首先一看就要用动态规划
我们设 f[i] 表示走到 i 这个位置可以得到的最大的冰冻指数
并可以简单地得到状态转移方程
f[j]=max{f[i]}+a[i],i+l≤j≤min(i+r,n)
然后我们打下去就可以得到60pts了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#define int long long
using namespace std;
const int maxn=200005;
int n,l,r;
int a[maxn];
int f[maxn];
signed main()
{
memset(f,-0x3f,sizeof(f));
cin>>n>>l>>r;
for(int i=0;i<=n;i++)
cin>>a[i];
f[0]=0;
for(int i=0;i<=n;i++)
{
for(int j=i+l;j<=i+r&&j<=n;j++)
f[j]=max(f[j],f[i]+a[j]);
}
int ans=-1e9;
for(int i=n-(r-l+1);i<=n;i++)
ans=max(f[i],ans);
cout<<ans<<'\n';
return 0;
}
|
接着我们观察状态转移方程 (1) ,发现这个状态转移方程实际上是要找一个最大的 f[j] 并且 j 属于一个区间
所以我们很容易就想到了滑动窗口的思想，单调队列
单调队列是什么呢？
如果队首超出了区间，那么队首弹出；如果队尾小于新要加进来的数字，那么队尾肯定不是要的最大值，所以把队尾弹出就可以了，然后最后要找的最大值肯定在队尾，这是单调的，可以证明
然后我们就可以写出来了
我写出来之后为了保证前 60pts 的分数正确，写了一个subtask，这个小技巧可以保证你能得到的分数一定会得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#define int long long
using namespace std;
const int maxn=200005;
int n,l,r;
int ans=-1e9;
int a[maxn];
int f[maxn];
int q[maxn],head,tail;
void task1()
{
head=1,tail=0;
for(int i=l;i<=n;i++)
{
while(head<=tail&&q[head]<i-r) head++;
while(head<=tail&&f[q[tail]]<f[i-l]) tail--;
q[++tail]=i-l;
f[i]=f[q[head]]+a[i];
if(i+r>n)
ans=max(f[i],ans);
}
cout<<ans<<'\n';
}
void task2()
{
memset(f,-0x3f,sizeof(f));
f[0]=0;
for(int i=0;i<=n;i++)
{
for(int j=i+l;j<=i+r&&j<=n;j++)
f[j]=max(f[j],f[i]+a[j]);
}
int ans=-1e9;
for(int i=n-(r-l+1);i<=n;i++)
ans=max(f[i],ans);
cout<<ans<<'\n';
}
signed main()
{
cin>>n>>l>>r;
for(int i=0;i<=n;i++)
cin>>a[i];
f[0]=0;
if(n<=10000) task2();
else task1();
return 0;
}
|
