飞扬的小鸟

发表于 | 分类于 | 评论数： | 阅读次数：

题目

这是题目

思路

看完数据范围之后发现，这题部分分还是不错的。（模拟赛想不到正解可以爆搜拿点分）

正解不难想，看得出是一个像背包一样的DP。

状态一维是横坐标，一维是纵坐标。$f[i][j]$ 表示到$(i,j)$ 这位置是最少要用的步数。

转移超简单，不多写了，细节看代码。（可以滚动数组优化一下空间）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int maxn=10007,maxm=1007,inf=1<<28;
inline int read(){
	int x=0,f=1;char C=getchar();
	while(!isdigit(C)) {if(C=='-') f=-1;C=getchar();}
	while(isdigit(C)) x=(x<<1)+(x<<3)+C-'0',C=getchar();
	return x*f;
}
int n,m,k,x[maxn],y[maxn],P[maxn],L[maxn],H[maxn];
int f[2][maxm],sum[maxn];
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++) L[i]=0,H[i]=m+1;
	for(int i=1;i<=k;i++)
	  P[i]=read(),L[P[i]]=read(),H[P[i]]=read(),
	  sum[P[i]]=1;
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	int now=0,pre=1;
	for(int i=1;i<=n;i++,now^=1,pre^=1){
//		cout<<i<<":----- "<<endl;
		for(int j=1;j<=m;j++) f[now][j]=inf;
		for(int j=x[i];j<H[i];j++)
		  if(j-x[i]>=0) f[now][j]=min(f[now][j],min(f[now][j-x[i]],f[pre][j-x[i]])+1);
		if(H[i]>m)
			for(int j=m-x[i]+1;j<=m;j++)
			  f[now][m]=min(f[now][m],min(f[now][j],f[pre][j])+1);
		for(int j=L[i]+1;j<H[i];j++)
		  if(j+y[i]<=m) f[now][j]=min(f[now][j],f[pre][j+y[i]]);
		bool F=1;
//		cout<<L[i]<<" "<<H[i]<<" -----"<<endl;
//		for(int j=1;j<=m;j++) cout<<j<<" "<<f[now][j]<<endl;
		for(int j=L[i]+1;j<H[i];j++)
		  if(f[now][j]<inf) F=0;
		if(F) {printf("0\n%d\n",sum[i-1]);return 0;}
		for(int j=0;j<=L[i];j++) f[now][j]=inf;
		for(int j=H[i];j<=m;j++) f[now][j]=inf;
	}
	int ans=inf;
	for(int i=L[n]+1;i<H[n];i++) ans=min(ans,f[pre][i]);
	printf("1\n%d\n",ans);
	return 0;
}
/*
2 1000 2
1 1000
1 1000
1 10 12
2 998 1000
*/