自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻zExNocs QQ 2436086691 欢迎交流＆骚扰

搬运于2025-08-24 21:32:08，当前版本为作者最后更新于2019-06-03 20:59:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一、杂言

我这个题解是按照从0开始的思路来讲的，比较适合于萌新，可能有些废话，所以请各位大犇们手下留情qwq

二、引入

这个题确实是细节题，毕竟是Noip提高组题还是非常不错的，有一些细节我在这列出来：(下面描述三中的"二中O"就是指这里面的注意点)

①高度为$M$时不能再上升

②可以多次点击，效果累加【因为无视了这句话写错了很多次QWQ

③管道不是按照顺序输入

④$M=0$不存在，但是$n$可以为0，而且鸟可以在(0,0~M)任何一个坐标开始

⑤管道输入的意思是下管道的上边界L与上管道的下边界H，也就是说这个两个管道分别占地为$(0,L)$和$(H,M)$

三、思路

这个题给出的状态有很多，那么很明显可以使用动态规划，可以列出的状态有：坐标$(x,y)$（分别对应目前的长度与高度）、点击次数、是否要点击。

1、状态确定&&转移方程(可以套模板)

假设没有管道，不妨设$dp[x][y][p]$为上一个点$(x-1,?)$点击或者不点击转移过来的坐标为$(x,y)$处的最小点击次数，其中$p=1$为点击，可以点击多次（二中②）,$p=0$为不点击。

由题设$up[i]$为$x=i$时点击一次上升高度，$down[i]$为$y=i$时不点击下降的高度。

那么当$p=1$时，$dp[x][y][1]=min(dp[x-1][y-up[x-1]][0or1],dp[x][y-up[x-1]][1])+1$

及要么从上一个点$x-1$点击一次过来，要么从本$x$坐标再点一次点出来。

当$p=0$时，$dp[x][y][0]=min(dp[x][y][1],dp[x-1][y+down[x-1]][0or1])$

及要么点，要么不点，而且$p=0$要在$p=1$已经确定的基础上选择 (即使在后面滚动数组p后也需要这样进行)。

很明显每次选取都是在$p=0 or 1$中选取最小值，那么可以滚动数组去掉p数组，上状态转移方程其他不变。

但是有一个要求，高度为$M$时不能再上升（二中①），那么我们可以进行一个特判，如果此时的$y>=m$，那么上述方程中使$y=m$，及 $dp[x][m]=min(dp[x][m],dp[x][y]),y∈(m,m+up[x-1])$

上述$x,y$都可以进行枚举。那么我们不难看出，去掉p维数组后这个状态方程跟背包神相似，没错，这个就是完全背包+01背包的双组合，那么可以记下: 如果遇见选择或者不选择状态的题目时，可以考虑背包，实在不会可以用我这个笨方法额外设个P数组0,1记录拿不拿状态，然后再优化删除，当然有的题也可能不能删除(这不就是01背包吗！)。

2、探究原题条件

现在又引入了一个叫做管道的鬼东西，那么我们需要再加一个特判。

如果这个地方是管道，也就是说这里不可以通过，那么就使这里的$dp[x][y]=inf$，不难写出代码：

for(int y=0;y<=low[cnt];y++)
	dp[x][y]=inf;
for(int y=high[cnt];y<=m;y++)
	dp[x][y]=inf;

$low[],high[]$如题目所述的$L$和$H$，$cnt$为当时遇见的第$cnt$个管道。（二中⑤）

这个特判是当$x=id[cnt]$时进行的，$id[cnt]$为第$cnt$个管道的$x$坐标。

另外要注意管道不是按照顺序输入（二中③），所以要把$low,high,id$写在同一个结构体中然后根据$id$进行$sort$

3、初始化

其实这个应该在状态转移方程里写的，但是我还是单独拉出来了 （其实是作者突然想起来还有初始化，懒得往上插了qwq）

memset(dp,inf,sizeof(dp));
for(int y=1;y<=m;y++)
	dp[0][y]=0;

三句话，没了。不过要注意的是$x$是从0开始的，所以要初始化在坐标$x=0$（注意点二中④）

4、判断何时撞墙和最终答案如何输出

很明显，撞的一定是管道上（因为$y=0$的时候我们根本就没考虑），所以每次在特判管道的时候再查询当前$x$坐标中$dp[x][y]$的最小值，如果最小值等于$inf$的话，那么肯定就撞到这个管道上了，那么此时就输出$0$和$cnt-1$。

为什么是$cnt-1$？，因为你撞到了第$cnt$个管道，这个管道你过不去，所以当然是通过了$cnt-1$个管道辣。

如果程序顺利通过的话，那么就直接再次寻找$dp[n][y],y∈(1,m)$的最小值就可以了。

5、更多优化&&部分代码细节

①、因为状态$dp[x][y]$一定是由$dp[x-1][?]$得到,并且$dp[x-1][?]$在推出$dp[x][y]$后没有任何作用，所以可以再次滚动数组，定义 i % 2 为$x$ , i%2^1(也可以为((i-1)%2)) 为$x-1$，那么我们就很愉快的把数组开到 $2*max$

相比之前的$max^2$内存少了很多，不过要注意可以去掉上述3中的初始化，改为在枚举$x$的时候加一条：

for(int y=0;y<=m;j++)
	dp[x%2][y]=inf;

仅仅只是在原来$O(n*m)$基础上加上了一个$m$，实际上对时间并没有太大的影响。

②、因为题目已经说明边界为$X=0$，所以枚举是从$X=1$的时候进行的，而且每次需要的是$up[x-1]$，我们不妨在初始化$up$数组的时候从$X=1$开始，那么我们使用的就是$up[x]$而不是$up[x-1]$了（实际上仅仅只是好看而已,不过也减少了计算量(你觉得计算一个减法能需要多长时间！)）

③、注意开$Y$数组大小的时候要开大一点，不要只局限于1005，因为咱们并不只是枚举到$M$，而是要枚举到$M+up[x]$

④、因为初始化 $dp[x][y]=inf$ ，所以在$p=1$(虽然p已经被删除了，不过为了方便说明还是把它写出来了)的时候不需要再加一个 $dp[x][y]=min(dp[x][y],dp[?][?]+1)$的情况，如果要点的话，必须要点一次，否则就是inf

⑤、剩下的细节请看下面的代码，不过代码的部分数组与上述描述的名字不一样（上面的名字是我为了方便讲解取得，下面代码懒得改了qwq）

6、$code$(你觉得直接抄可以过吗？qwq):

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define gc(a) a=getchar()
#define pc(a) putchar(a)
ll read(){
    char c;ll x=0;bool flag=0;gc(c);
    while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),gc(c);}
    return flag?-x:x;
}
void pr(ll x){
    if(x<0){x=-x;pc('-');}
    if(x>9) pr(x/10);
    pc(x%10+48);
}
//-------快读------
#define inf 0x3f3f3f3f
const ll maxn=10005;
const ll maxm=10005;
struct node
{
	ll id,h,l;
	bool operator <(const node &a) const
	{
		return id<a.id;
	}
}o[maxn];
ll x[maxn],y[maxn],dp[2][maxm],n,m,k,cnt=1,ans;
int main()
{
	//memset(dp,inf,sizeof(dp));//两个被遗忘的初始化之一qwq
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)
	x[i]=read(),y[i]=read();
	for(int i=1;i<=k;i++)
	o[i].id=read(),o[i].l=read(),o[i].h=read();
	sort(o+1,o+k+1);//管道id排序!
	//for(int i=1;i<=m;i++)
	//dp[0][i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)//注意要初始化！
		dp[i%2][j]=inf;
		for(int j=x[i]+1;j<=x[i]+m;j++)//p=1，完全背包
		dp[i%2][j]=min(dp[i%2^1][j-x[i]]+1,dp[i%2][j-x[i]]+1);
		for(int j=m+1;j<=x[i]+m;j++)//比m大的都是m
		dp[i%2][m]=min(dp[i%2][m],dp[i%2][j]);
		for(int j=1;j<=m-y[i];j++)//p=0，01背包
		dp[i%2][j]=min(dp[i%2][j],dp[i%2^1][j+y[i]]);
		if(i==o[cnt].id)//如果这个地方有管道
		{
			ans=inf;//主要每次都要初始化一次！
			for(int j=0;j<=o[cnt].l;j++)
			dp[i%2][j]=inf;
			for(int j=o[cnt].h;j<=m;j++)
			dp[i%2][j]=inf;
			for(int j=1;j<=m;j++)//寻找是否可以通过
			ans=min(dp[i%2][j],ans);
			if(ans==inf)
			{
				pr(0);pc('\n');pr(cnt-1);return 0;
			}
			cnt++;
		}
	}
	ans=inf;//注意要初始化！
	for(int j=1;j<=m;j++)
	ans=min(dp[n%2][j],ans);
	pr(1);pc('\n');pr(ans);
	return 0v0;
}

4、后语

题解千万条，细节第一条

题解没有赞，作者两行泪

你看作者因为写题解都把上面的数字记成4了，你们忍心咩qwq