• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【解题报告】洛谷P1725 琪露诺

开发技术 开发技术 2天前 3次浏览

【解题报告】洛谷P1725 琪露诺

题目链接

https://www.luogu.com.cn/problem/P1725

思路

这道题目首先一看就要用动态规划

我们设 (f[i]) 表示走到 (i) 这个位置可以得到的最大的冰冻指数

并可以简单地得到状态转移方程

[f[j]=max{f[i]}+a[i],i+l le j le min(i+r,n)
]

然后我们打下去就可以得到60pts了

#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,这个小技巧可以保证你能得到的分数一定会得到

#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;
}

程序员灯塔
转载请注明原文链接:【解题报告】洛谷P1725 琪露诺
喜欢 (0)