记录编号	327228	评测结果	WWWWWWAAWWWWWWWWWWWW
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	10
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	2.316 s
提交时间	2016-10-21 21:00:31	内存使用	33.19 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010,maxm=1010;
int n,m,k,x[maxn],y[maxn],a[maxn],high[maxn],low[maxn],f[maxn][maxm],ans=~(1<<31),tmp=0;//f[i][j]表示走到了第i列第j行的最少点击屏幕数
int main(){
#define MINE
#ifdef MINE
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		high[i]=m+1;
		low[i]=0;
	}
	high[n+1]=m+1;
	low[n+1]=0;
	while(k--){
		int x;
		scanf("%d",&x);x++;
		a[x]++;
		scanf("%d%d",&low[x],&high[x]);
	}
	memset(f,63,sizeof(f));
	for(int j=1;j<=m;j++)f[0][j]=0;
	for(int i=1;i<=n+1;i++){
		a[i]+=a[i-1];
		for(int j=low[i]+1;j<high[i];j++){
			f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
			if(j>x[i]){
				f[i][j]=min(f[i][j],f[i-1][j-x[i]+1]);
				f[i][j]=min(f[i][j],f[i][j-x[i]]+1);
			}
			if(f[i][j]<0x3f3f3f3f){
				tmp=max(tmp,a[i]);
				if(i==n+1)ans=min(ans,f[i][j]);
			}
			//printf("f[%d][%d]=%d\n",i,j,f[i][j]);
		}
	}
	if(ans<0x3f3f3f3f)printf("1\n%d",ans);
	else printf("0\n%d",tmp);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
/*
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
Answer:
1
6
*/
/*
注意这玩意儿是完全背包。
*/