一、题目

点此看题

有一个 \(2\times n\) 的网格图，有 \(m_1+m_2\) 个障碍分别在上下两行，现在你驾驶坦克要从 \((1,0)\) 走到 \((1,n+1)\) 或者 \((2,n+1)\)，每秒你可以选择是否换行（列不变），然后选择是否开炮，再往前行进一格。

开炮会摧毁水平右方第一个还没被摧毁的障碍物，开炮需要 \(t\) 秒冷却，初始时需要冷却。现在问你是否能到达终点，如果能则输出过程中每一个转弯和开炮的位置。

\(n\leq 10^9,m_1+m_2\leq 10^6\)

二、解法

考虑按题目描述中开炮需要记录哪些障碍被摧毁，极其不方便，究其原因是在开炮时决策打后面的障碍物是不清晰的，那么考虑延迟决策的思想，在遇到障碍物时再考虑开炮。

把这个思想应用到只有一行的简单情况，我们没走一格就会积攒一点能量，开炮会消耗 \(t\) 点能量，那么我们在下一格是障碍的时候再开炮，注意现在决策开炮就相当于以前开了一次炮。

回到本题，我们只需要考虑换行会能量的影响，因为换行之后我们只能利用原先的能量打出一颗炮弹，所以需要把当前的能量和 \(t\) 取 \(\min\) 即可。

现在就可以用 \(dp\) 做它了，设 \(f[i][j]\) 表示到 \((i,j)\) 的最大能量，首先我们把障碍物的列和它的下一列全部取出来离散化，转移先考虑转向，再考虑下一格有无障碍物，如果有就需要开炮，时间复杂度 \(O(n)\)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 2000005;
#define pb push_back
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,m1,m2,k,a[M],x1[M],x2[M];
int ob[2][M],f[2][M],g[2][M];
vector<int> z1;vector<pair<int,int>> z2;
void trans(int j,int i,int v,int op)
{
	if(f[j][i]<v) f[j][i]=v,g[j][i]=op;
}
signed main()
{
	n=read();m1=read();m2=read();k=read();
	for(int i=1;i<=m1;i++)
		a[++m]=x1[i]=read(),a[++m]=x1[i]+1;
	for(int i=1;i<=m2;i++)
		a[++m]=x2[i]=read(),a[++m]=x2[i]+1;
	a[++m]=n+1;sort(a+1,a+1+m);
	m=unique(a+1,a+1+m)-a-1;
	memset(f,-1,sizeof f);
	for(int i=1;i<=m1;i++)
		ob[0][lower_bound(a+1,a+1+m,x1[i])-a]=1;
	for(int i=1;i<=m2;i++)
		ob[1][lower_bound(a+1,a+1+m,x2[i])-a]=1;
	f[0][0]=f[1][0]=0;g[1][0]=1;
	for(int i=0;i<m;i++)
	{
		//consider changing the line
		for(int j=0;j<2;j++)
			if(~f[j][i] && !ob[j^1][i])
				trans(j^1,i,min(f[j][i],k),1);
		//consider fucking the obstacles
		for(int j=0;j<2;j++)
			if(~f[j][i] && f[j][i]+a[i+1]-a[i]-1>=k*ob[j][i+1])
				trans(j,i+1,f[j][i]+a[i+1]-a[i]-k*ob[j][i+1],0);
	}
	int x=0,y=m,now=2e9;
	if(~f[0][y]) x=0;else x=1;
	if(f[x][y]==-1) {puts("No");return 0;}
	while(x+y)
	{
		if(g[x][y]) z1.pb(a[y]),x^=1;
		else
		{
			if(ob[x][y]) now=min(now-k,a[y]-1),
				z2.pb(make_pair(now,x+1));
			y--;
		}
	}
	puts("Yes");
	reverse(z1.begin(),z1.end());
	reverse(z2.begin(),z2.end());
	printf("%d\n",z1.size());
	for(auto x:z1) printf("%d ",x);
	printf("\n%d\n",z2.size());
	for(auto x:z2) printf("%d %d\n",x.first,x.second);
}