垃圾陷阱 && [NOIP2014 提高组] 飞扬的小鸟

#include<bits/stdc++.h>

using namespace std;

int d,n,dp[1010];

struct node{int t,f,h;} a[1010];

bool cmp(node aa,node bb){ return aa.t<bb.t; }

int main()

{

	scanf("%d%d",&d,&n);

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

	{

		scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);

	}

	sort(a+1,a+n+1,cmp);

	dp[0]=10;//某一深度的血量

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

	{

		for(int j=d;j>=0;j--)

		{

			if(dp[j]>=a[i].t)//血量=时间

			{

				if(j+a[i].h>=d)

				{

					printf("%d",a[i].t);

					return 0;

				}

				dp[j+a[i].h]=max(dp[j+a[i].h],dp[j]);//垫

				dp[j]+=a[i].f;//吃

			}

		}

	}

	printf("%d",dp[0]);

	return 0;

}

[NOIP2014 提高组] 飞扬的小鸟：

把无限点击换成完全背包，下降换成01背包，无法到达就是点正无穷次

#include<bits/stdc++.h>

using namespace std;

int n,m,k;

bool vis[100010];

int dp[10010][2010];//在坐标 i,j 处未经处理时的点击次数 j 会超过 m ,so开到2000

struct move{int x,y;}a[100010];

int low[100010],hi[100010];

int main()

{

	scanf("%d%d%d",&n,&m,&k);

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

	{

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	for(int i=1;i<=n;i++) low[i]=1,hi[i]=m;

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

	{

		int u,v,w;

		scanf("%d%d%d",&u,&v,&w);

		vis[u]=1;

		low[u]=v+1;

		hi[u]=w-1;

	}

	memset(dp,0x3f,sizeof(dp));

	for(int i=1;i<=m;i++) dp[0][i]=0;

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

	{

		for(int j=a[i].x+1;j<=m+a[i].x;j++)

			dp[i][j]=min(dp[i-1][j-a[i].x],dp[i][j-a[i].x])+1;

		for(int j=m+1;j<=m+a[i].x;j++)

			dp[i][m]=min(dp[i][m],dp[i][j]);

		for(int j=1;j<=m-a[i].y;j++)

			dp[i][j]=min(dp[i][j],dp[i-1][j+a[i].y]);

		for(int j=1;j<low[i];j++) dp[i][j]=1e9;

		for(int j=hi[i]+1;j<=m;j++)  dp[i][j]=1e9;

	}

	int ans=1e9;

	for(int i=1;i<=m;i++) ans=min(ans,dp[n][i]);

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

	else

	{

		int i,j;

		for(i=n;i>=1;i--)

		{

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

			{

				if(dp[i][j]<1e9) break;

			}

			if(j<=m) break;

		}

		ans=0;

		for(j=1;j<=i;j++)

			if(vis[j])ans++;

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

	}

	return 0;

}

巴特西

垃圾陷阱 && [NOIP2014 提高组] 飞扬的小鸟

最新文章

热门文章