题解：P9691 [GDCPC 2023] Base Station Construction

思路

First

~~一眼 DP。~~

Second

设

dp_i

表示对于前

i

个位置，选择第

i

个位置的答案最小值。

考虑如何转移。

可以想象转移方程的样子大概是

dp_i = \min_{j=Left_i}^{Right_i} dp_j + a_i

，且显然

Right_i = i-1

。

所以接下来的任务是对于每个

i

，找到可以往

i

转移的下界。

考虑什么样的

j

可以向

i

转移。显然当且仅当不存在

k \in [1,m]

，使得

j < L_k \le R_k < i

。

即对于所有的

k

，

R_k < i

，有

j \ge \max L_k

。

所以

Left_i = \max L_k

，其中

R_k < i

。

这样 DP 方程就结束了。

此时复杂度

O(n^2)

。

Third

本题重点——单调队列优化 DP，来了！

不会单调队列的不妨看一下这个题。

~~然后就没有然后了。~~

思考单调队列过程时，现在在点

i

。

如果 q.front()<Left[i]，就 q.pop()。

然后转移，最后加入

i

。

最终复杂度

O(n)

。

Last

这时候有人就问了：所以最终状态是什么呢？

这里比较巧妙，在给定的

n

个点后新建一个点，权值为

0

（即

a_{n+1} = 0

）。

最终答案就是

dp_{n+1}

。

~~最终有一些不可缺少的东西。~~

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

namespace Memory_Love{
	int read(){ int x=0; bool flag=1; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
		return flag? x:-x;}
	void write(int x,char ch=0){if(x<0) x=-x,putchar('-');
		static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
		while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
	int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
	int lcm(int a,int b){return a/gcd(a,b)*b;}
} using namespace Memory_Love;
const int N=5e5+5;
int n,m;
int a[N],L[N],R[N];

namespace DP
{
	int last[N],dp[N];
	deque<int> q;
	void init()
	{
		int i; a[++n]=0;
		while(q.size()) q.pop_back();
		for(i=1;i<=n;i++) last[i]=0;
		for(i=1;i<=m;i++) last[R[i]+1]=max(last[R[i]+1],L[i]);
		for(i=1;i<=n;i++) last[i]=max(last[i],last[i-1]);
	}
	int solve()
	{
		int i;
		q.push_back(0);
		for(i=1;i<=n;i++)
		{
			while(q.size() && q.front()<last[i])
			q.pop_front();
			dp[i]=dp[q.front()]+a[i];
			while(q.size() && dp[q.back()]>dp[i])
			q.pop_back();
			q.push_back(i);
		}
		return dp[n];
	}
}

int solve()
{
	int i;
	n=read();   for(i=1;i<=n;i++) a[i]=read();
	m=read();   for(i=1;i<=m;i++) L[i]=read(),R[i]=read();
	DP::init(); return DP::solve();
}

bool Ending;
signed main()
{
	int T=read(); while(T--) write(solve(),'\n');
	cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
	return 0;
}

题解：P9691 [GDCPC 2023] Base Station Construction

文章操作

思路

First

Second

Third

Last

相关推荐

评论

题解：P9691 [GDCPC 2023] Base Station Construction