luoguP1941-

20分&50分：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 20005;

int n,m,k,x[N],y[N],ans,sum,book[N];

int f[10005][1005];

struct node{

	int p,l,h;

}v[N];

bool flag;

inline int read()

{

	int ans=0,w=1;

	char c=getchar();

	while((c<'0'||c>'9')&&c!='-') c=getchar();

	if(c=='-') { w=-1; c=getchar(); }

	while(c>='0'&&c<='9')

	{ ans=ans*10+c-'0'; c=getchar(); }

	return ans*w;

}

int min(int a,int b)

{ if(a<b) return a; return b; }

int max(int a,int b)

{ if(a>b) return a; return b; }

bool cmp(node a,node b)

{ return a.p<b.p; }

void dfs(int t,int high,int ansp,int sumt)

{

    high=min(high,m);

	if(ansp>ans) return ;

	if(high<=0) return ;

	if(book[t])

	{ if(high>=v[book[t]].h||high<=v[book[t]].l) return ; }

	if(t>=n) { flag=1; ans=min(ans,ansp); return ;}

	if(book[t]) ++sumt;

	sum=max(sum,sumt);

	dfs(t+1,high-y[t],ansp,sumt);

	for(int i=1;i<=3;i++)

	 dfs(t+1,high+i*x[t],ansp+i,sumt);

}

void print(int u)

{

	int sum=0;

	for(int i=0;i<=u;i++)

	if(book[i]) ++sum;

	printf("0\n%d\n",sum);

	return ;

}

void work()

{

	for(int i=1;i<=n;i++)

	 for(int j=0;j<=m;j++)

	  f[i][j]=-1;

	f[0][0]=-1;

	for(int i=1;i<=n;i++)

	{

		bool fg=0;

		int ll,rr;

		if(book[i]) ll=v[book[i]].l+1,rr=v[book[i]].h-1;

		else ll=1,rr=m;

		for(int j=ll;j<=rr;j++)

		{

			if(j==m)

			{

				for(int k=1;k<=m;k++)

				if(f[i-1][k]>=0)

				{

					fg=1;

					if(f[i][j]>=0) f[i][j]=min(f[i][j],f[i-1][k]+(m-k)/x[i-1]+((m-k)%x[i-1]!=0));

					else f[i][j]=f[i-1][k]+(m-k)/x[i-1]+((m-k)%x[i-1]!=0);

				}

				break;

			}

			if(f[i-1][j+y[i-1]]>=0&&j+y[i-1]<=m) f[i][j]=f[i-1][j+y[i-1]],fg=1;

			for(int k=1;k<=j/x[i-1];k++)

			{

				if(f[i-1][j-k*x[i-1]]>=0&&(j-k*x[i-1])>0)

				{

					fg=1;

					if(f[i][j]>=0) f[i][j]=min(f[i][j],f[i-1][j-k*x[i-1]]+k);

					else f[i][j]=f[i-1][j-k*x[i-1]]+k;

				}

			}

		}

		if(!fg) { print(i-1); return ;}

	}

	int t=0;

	while(f[n][t]<0) ++t;

	int anst=f[n][t];

	for(int i=t+1;i<=m;i++)

	if(f[n][i]>=0)

	 anst=min(anst,f[n][i]);

	printf("1\n%d\n",anst);

	return ;

}

int main()

{

	printf("%d\n",sizeof(f)>>20);

	freopen("bird.in","r",stdin);

	freopen("bird.out","w",stdout);

	ans=100005;

	n=read(); m=read(); k=read();

	for(int i=0;i<n;i++)

	 x[i]=read(), y[i]=read();

	for(int i=1;i<=k;i++)

	 v[i].p=read(),v[i].l=read(),v[i].h=read();

	sort(v+1,v+k+1,cmp);

	for(int i=1;i<=k;i++)

	 book[v[i].p]=i;

	if(n<10) { work(); return 0; }

	if(v[1].p==0&&k!=0) //50分 改之前: if(v[1].p==0) 20分

	{//cout<<"*";

		for(int i=v[1].l+1;i<v[1].h;i++)

		 dfs(0,i,0,0);

	}

	else

	{

		for(int i=1;i<=m;i++)

		 dfs(0,i,0,0);

    }

    if(flag) printf("1\n%d\n",ans);

    else printf("0\n%d\n",sum);

    return 0;

}

(考场写法)

80分：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 100005;

int inf=2147483647;

int n,m,k,f[10005][1005];//f[i][j] 表示到第i步，j高度至少要跳几步

int x[N],y[N],book[N],anst=inf;

struct node{

	int p,l,h;

}v[N];

inline int read()

{

	int ans=0,w=1;

	char c=getchar();

	while((c<'0'||c>'9')&&c!='-') c=getchar();

	if(c=='-') { w=-1; c=getchar(); }

	while(c>='0'&&c<='9')

	{ ans=ans*10+c-'0'; c=getchar(); }

	return ans*w;

}

int min(int a,int b)

{ if(a<b) return a; return b; }

int max(int a,int b)

{ if(a>b) return a; return b; }

bool cmp(node a,node b)

{ return a.p<b.p; }

void print()

{

	bool flag=0;

	for(int i=1;i<=k;i++)

	{

		flag=0;

		for(int j=1;j<=m;j++)

		 if(f[v[i].p][j]<inf) { flag=1; break;}

		if(!flag) { printf("0\n%d\n",i-1); return ;}

	}

}

int main()

{

	freopen("bird.in","r",stdin);

	freopen("bird.out","w",stdout);

	n=read(); m=read(); k=read();

	for(int i=0;i<n;i++)

	 x[i]=read(),y[i]=read();

	for(int i=1;i<=k;i++)

	 v[i].p=read(),v[i].l=read(),v[i].h=read();

	sort(v+1,v+k+1,cmp);

	for(int i=1;i<=k;i++) book[v[i].p]=i;

	memset(f,0x7f,sizeof(f));

	inf=f[0][0];

	int ll,rr;

	if(book[0]) ll=v[book[1]].l+1,rr=v[book[1]].h-1;

	else ll=1,rr=m;

	for(int i=ll;i<=rr;i++) f[0][i]=0;

	for(int i=1;i<=n;i++)

	{

		if(book[i]) ll=v[book[i]].l+1,rr=v[book[i]].h-1;

		else ll=1,rr=m;

		for(int j=ll;j<=rr;j++)

		{

			if(j==m)

			{

				for(int z=m-x[i-1];z<=m;z++)

				{

					f[i][j]=min(f[i][j],f[i-1][z]+1);

					f[i][j]=min(f[i][j],f[i][z]+1);

				}

			}

			if(j+y[i-1]<=m)

			  f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);

			if(j-x[i-1]>0)

			  f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1),

			  f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);

		}

	}

	for(int i=1;i<=m;i++)

	 anst=min(anst,f[n][i]);

	if(anst<inf) printf("1\n%d\n",anst);

	else print();

	return 0;

}

(题解思路)