专栏文章

P1941 [NOIP2014 提高组] 飞扬的小鸟

RRt__
P1941题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir39ge7
此快照首次捕获于
2025/12/04 15:02
3 个月前
此快照最后确认于
2025/12/04 15:02
3 个月前
查看原文
P1941 [NOIP2014 提高组] 飞扬的小鸟

题意简述

给定一个游戏界面的高和宽，其中碰到上边界将不能再上升，而碰到下边界会直接死亡。又给定了一些柱子的横坐标和上下边界，小鸟在飞行时只能从中间穿过，不能碰到上下边界。求是否能到达右边。能，则输出最少的点击次数；不能，则输出最多通过的柱子数。
给定每个位置的 upi,downiup_i, down_i其中小鸟只能向上移动任意次 upiup_i 或一次 downidown_i，只有 upiup_i 需要点击。

思路

90tps

考虑 DP。对于每个位置，我们可以记录到达该位置需要点击的最少次数。设 fi,jf_{i,j} 为到达位置 (x,y)(x, y) 需要点击的最少次数，我们可以推出状态转移方程：
fi,j=max⁡(fi−1,j−k×upi−1+k,fi−1,j+downi−1)f_{i,j} = \max(f_{i - 1, j - k\times up_{i - 1}} + k, f_{i - 1, j + down_{i - 1}})
由于每个位置只有他的上一个位置转移过来，所以我们自然可以用滚动数组优化（不用也不影响）。时间复杂度 O(n2)O(n^2)，预计得分 70tps70tps（考场上感觉不少就直接跳过去做下一题了，事实上是 90tps90tps）。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read(){
	ll res = 0, f = 1;
	char c = getchar();
	while(c > '9' || c < '0'){
		if(c == '-')f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * f;
}

const int N = 100010, M = 10010;
ll up[N], down[N];
struct ii{
	ll h, l;
	int ii;
}qu[N];
ll f[3][M];

signed main(){
	ll n = read(), m = read(), k = read();
	for(int i = 0; i < n; i ++){
		up[i] = read(), down[i] = read();
	}
	for(int i = 1; i <= k; i ++){
		ll x = read(), l = read(), h = read();
		qu[x] = {h - 1, l + 1};
	}
	for(int i = 1; i <= n; i ++){
		if(qu[i]. h == 0){
			qu[i]. h = m;
			qu[i]. l = 1;
			qu[i]. ii = qu[i - 1]. ii;
		}
		else{
			qu[i]. ii = qu[i - 1]. ii + 1;
		}
		
	}
	memset(f, 0x3f, sizeof f);
	for(int i = 1; i <= m; i ++){
		f[0][i] = 0;
	}
	qu[0] = {m, 1};
	for(int i = 0; i < n; i ++){
		bool flag = 0;
		for(int j = 1; j <= m; j ++)f[(i + 1) & 1][j] = 0x3f3f3f3f3f3f3f3f;
		for(int j = qu[i]. l; j <= qu[i]. h; j ++){
			if(f[i & 1][j] == 0x3f3f3f3f3f3f3f3f)continue;

			if(j - down[i] >= qu[i + 1]. l && j - down[i] <= qu[i + 1]. h){
				f[(i + 1) & 1][j - down[i]] = min(f[(i + 1) & 1][j - down[i]], f[i & 1][j]);
				flag = 1;
			}
			if(qu[i + 1]. h < qu[i]. l)continue;
			ll sta = (qu[i + 1]. l - j) / up[i];
			if((qu[i + 1]. l - j) % up[i])sta ++;
			sta = max(1ll, sta);
			ll endd = (qu[i + 1]. h - j) / up[i];
			if(qu[i + 1]. h == m && (qu[i + 1]. h - j) % up[i]){
				endd ++;
			}

			for(int k = sta; k <= endd; k ++){
				ll hh = min(m, j + up[i] * k);
				flag = 1;
				f[(i + 1) & 1][hh] = min(f[(i + 1) & 1][hh], f[i & 1][j] + k);

			}
		}
		if(!flag){
			cout << 0 << endl << qu[i]. ii;
			return 0;
		}
	}
	
	ll ans = 0x3f3f3f3f3f3f3f3f;
	for(int j = qu[n]. l; j <= qu[n]. h; j ++){
		ans = min(ans, f[n & 1][j]);
	}
	cout << 1 << endl;
	cout << ans;
	return 0;
}

100tps

我们观察上升和下降的规则，可以发现，上升的过程和完全背包有着惊人的相似度，而下降的过程几乎就是我们熟悉的 0101 背包。由此，我们可以得出一个做法：将上升和下降分开处理，分别做完全和 0101 背包。
完全背包（上升）的第二次以及更多的点击可以直接从 fi,j−upi−1f_{i, j - up_{i - 1}} 转移，只有点一次是从 fi−1,j−upi−1f_{i-1,j - up_{i-1}} 转移的（完全背包 n2n^2 法）；而 0101 背包是从 fi−1,j−upi−1f_{i - 1, j - up_{i - 1}} 转移的。
记得特判一下顶到最上面的情况。

代码

CPP
#include<bits/stdc++.h>
#define N 10005
using namespace std;
#define ll long long
int n,m,k,x[N],y[N],low[N],high[N],f[N][2005];
bool flag[N];

inline ll read(){
	ll res = 0, f = 1;
	char c = getchar();
	while(c > '9' || c < '0'){
		if(c == '-')f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * f;
}

int main(){
	n = read(), m = read(), k = read();
	for (int i = 1; i <= n; i ++) x[i] = read(), y[i] = read();
	for (int i = 1; i <= n; i ++){
		high[i] = m;
		low[i] = 1;
	}
	for (int i=1;i<=k;i++){
		int xx = read(), yy = read(), zz = read();
		flag[xx] = 1;
		low[xx] = yy + 1;
		high[xx] = zz - 1;
	}
	memset(f, 0x3f3f3f, sizeof(f));
	for (int i = 1; i <= m; i ++) f[0][i]=0;
	for (int i = 1; i <= n; i ++){
		for (int j = x[i] + 1; j <= x[i] + m; j ++) 
			f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1);
		for (int j = m + 1; j <= x[i] + m; j ++)
			f[i][m] = min(f[i][m], f[i][j]);
		for (int j = 1; j <= m - y[i]; j ++)
			f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);
		for (int j = 1;j < low[i]; j ++)
			f[i][j] = 0x3f3f3f;
		for (int j = high[i] + 1; j <= m; j++)
			f[i][j] = 0x3f3f3f;
	}
	int ans=0x3f3f3f;
	for (int i = 1;i <= m; i ++) ans = min(ans, f[n][i]);
	if (ans < 0x3f3f3f){
		cout << 1 << endl << ans;
		return 0;
	}
	int i, j;
	for (i = n; i >= 1; i --){
		for (j = 1; j <= m; j ++)
			if (f[i][j] < 0x3f3f3f) break;
		if (j <= m) break;
	}
	ans = 0;
	for (j = 1;j <= i; j ++)
		if (flag[j]) ans ++;
	cout << 0 << endl << ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...