记录编号	440230	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.641 s
提交时间	2017-08-22 20:32:03	内存使用	77.14 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=10005;
int n,m,k,up[inf],down[inf],a[inf][1005],f[inf][1005],s[inf];
int main()
{
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	memset(f,0x3f,sizeof(f));
	for(int i=0;i<n;i++){
		scanf("%d%d",&up[i],&down[i]);
	}
	for(int i=1;i<=k;i++){
		int p,l,h;
		scanf("%d%d%d",&p,&l,&h);
		s[p]++;
		for(int j=0;j<=l;j++){
			a[p][j]=1;
		}
		for(int j=h;j<=m;j++){
			a[p][j]=1;
		}
	}
	for(int i=1;i<=m;i++){
		if(!a[0][i])
		f[0][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=up[i-1]+1;j<m;j++){
			f[i][j]=min(f[i][j],min(f[i-1][j-up[i-1]],f[i][j-up[i-1]])+1);
		}
			for(int j=m-up[i-1];j<=m;j++){
				f[i][m]=min(f[i][m],min(f[i-1][j],f[i][j])+1);
			}
		for(int j=1;j+down[i-1]<=m;j++){
			f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);
		}
		for(int j=1;j<=m;j++)//一开始我是没有这句的而是直接在循环里面判断a[i][j]是否被标记，我还以为这两种写法是等价的
		//卡了我n天，后来我发现，假设当前点为i，j，他可以从i-1,j-2*up[i-1]转移过来,但i,j-up[i-1]是墙，如果按我之前写法
		//直接判断标记continue掉，墙的位置不会被更新，i,j,也不会被更新，他只会被i-1,j-up[i-1]，和i,j-up[i-1]更新 
		// 但i,j-up[i-1]是墙，没被更新，事实上连点两下可以通过i-1,j-2*up[i-1]转移而来，但按我之前写法却没有
		//所以挽救方法就是先不判墙，让他能更新的全部更新，最后再为有墙的地方重新赋值f[0][0] 
		if(a[i][j])f[i][j]=f[0][0];
	}
	int mi=0x3fffffff;
	for(int i=1;i<=m;i++){
		mi=min(mi,f[n][i]);
	}
	if(mi!=f[0][0]){
		cout<<1<<endl<<mi;
	}
	else{
		cout<<0<<endl;
		int book=0;
		int o;
		for(int i=n;i>=0;i--){
			for(int j=m;j>=1;j--){
				if(f[i][j]!=f[0][0]){
					o=i;
					book=1;
					break;
				}
			}
			if(book)
			break;
		}
		int ans=0;
		for(int i=o;i>=0;i--)
		if(s[i])ans++;
		cout<<ans;
	}
	return 0;
}