【NOIP2014 Day1 T3】飞扬的小鸟

【NOIP2014 Day1 T3】飞扬的小鸟

Time Limit:20000MS  Memory Limit:131072K
Total Submit:58 Accepted:14 
Case Time Limit:1000MS

Description

 

Input

 

Output

 

Sample Input

样例输入1：
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

样例输入2：
10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10

Sample Output

样例输出1：
1
6

样例输出2：
0
3

Hint

 

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 10005
#define maxm 1005
#define inf 1<<25
using namespace std;
int f[maxn][maxm],up[maxn],down[maxn],top[maxn],tail[maxn];
int n,m,tt,ans=0;
int main()
{
	int i,j,k,t,Min=inf;
	bool mark;
	scanf("%d%d%d",&n,&m,&tt);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&up[i],&down[i]);
		top[i]=m+1;
		for(j=0;j<=m;j++)f[i][j]=inf;
	}
	for(i=1;i<=tt;i++)
	{
		scanf("%d",&t);
		scanf("%d%d",&tail[t],&top[t]);
	}
	for(i=1;i<=n;i++)
	{
		mark=0;
		for(j=0;j<=m;j++)
			if(j-up[i]>0)
				f[i][j]=min(f[i][j-up[i]]+1,min(f[i][j],f[i-1][j-up[i]]+1));
			
		for(j=max(0,m-up[i]);j<=m;j++)
			f[i][m]=min(f[i][j]+1,min(f[i][m],f[i-1][j]+1));
				
		for(j=0;j<=m;j++)
			if(j+down[i]<=m)f[i][j]=min(f[i][j],f[i-1][j+down[i]]);
			
//		for(j=1;j<=m;j++)printf("%d ",f[i][j]);
//		putchar(10);
		for(j=0;j<=tail[i];j++)f[i][j]=inf;
		for(j=top[i];j<=m;j++)f[i][j]=inf;
		
//		for(j=1;j<=m;j++)printf("%d ",f[i][j]);
//		putchar(10);
		
		for(j=tail[i]+1;j<top[i];j++)
			if(f[i][j]<inf){mark=1;break;}
		if(!mark){printf("0\n%d\n",ans);return 0;}
		if(top[i]!=m+1||tail[i]!=0)ans++;
//		printf("%d--%d\n",i,ans);
	}
	for(j=tail[n]+1;j<top[n];j++)Min=min(f[n][j],Min);
	printf("1\n%d\n",Min);
	return 0;
}

————dp————

dp[i][j]=min(dp[i][j],dp[i-1][j-up[i]]+1);

1.dp[i][j]=min(dp[i][j],k*dp[i-1][j-up[i]]+1);//过不完所有数据，会超时；

2.dp[i][j]=min(dp[i][j],dp[i][j-up[i]]+1);//太机智了，完全背包（以后注意都这样写，也算一个优化）；