洛谷P1156 垃圾陷阱

两种状态表示方法。

①设f(i,j):处理完前i件垃圾，体力值为j的最大高度。

先按时间顺序排好序，设a[i].t为第i件垃圾出现时间，a[i].h为第i件垃圾的高度，a[i].f为第i件垃圾所提供体力值。

则f[i][j]= max{

-1 ，状态不存在

f[i-1][j+a[i].t-a[i-1].t]+a[i].h ，f[i-1][j+a[i].t-a[i-1].t] ≠ -1

f[i-1][j+a[i].t-a[i-1].t-a[i].f] ， j>=a[i].f并且f[i-1][j+a[i].t-a[i-1].t-a[i].f] ≠ -1

}

注意有可能用完全部垃圾还没跳出去，通过最后判断ans来找到最后时间。

刚开始想用刷表法，但越想越写，越绕越晕，大概还是填表法适合背包吧。

递推时要注意，上不越界，下不越界，条件满足才能转移，小心转移到不合法或不应该转移去的位置。比如这题要不是洛谷可以看数据分析bug，漏了 j>=a[i].f这一条是非常难找到的。

#include<bits/stdc++.h>
using namespace std;

int d,g,f[155][3505],ans;
struct rubbish{
	int t,f,h;
	bool operator < (rubbish x){
		return t<x.t;
	}
}a[105];

int main()
{
	freopen("input.in","r",stdin);
//	freopen("output.out","w",stdout);
	cin>>d>>g;
	for(int i=1;i<=g;i++)cin>>a[i].t>>a[i].f>>a[i].h;
	sort(a+1,a+1+g);  
	memset(f,-1,sizeof(f));
	f[0][10]=0;
	for(int i=1;i<=g;i++)for(int j=0;j<=3000;j++)
	{
		if(f[i-1][j+a[i].t-a[i-1].t]>=0)f[i][j]=f[i-1][j+a[i].t-a[i-1].t]+a[i].h;
		if(j>=a[i].f )f[i][j]=max(f[i][j],f[i-1][j+a[i].t-a[i-1].t-a[i].f]);
	}
    //for(int i=1;i<=g+1;i++)for(int j=0;j<=30;j++)printf("f[%d][%d]=%d\n",i,j,f[i][j]);
	for(int i=1;i<=g;i++)
	{
		int flag1=0,flag2=1;//1:jump out,2:died
		for(int j=0;j<=3000;j++)
		{
			if(f[i][j]>=d){flag1=1;break;}
			if(f[i][j]>=0){flag2=0;break;}
		}
		if(flag1){ans=a[i].t;break;}
		if(flag2)
		{
			int j;
			for(j=3000;j>=0;j--)if(f[i-1][j]>=0)break;
			ans=a[i-1].t+j;
			break;
		}
	}
	if(!ans)
	{
		int j;
		for(j=3000;j>=0;j--)if(f[g][j]>=0)break;
		ans=a[g].t+j;
	}
	cout<<ans<<endl;
//	for(int i=1;i<=g;i++)cout<<a[i].t<<" "<<a[i].f<<" "<<a[i].h<<"\n";
	return 0;
}

②设f(i,j):前i件垃圾，高度为j的最大体力值。转移方程在代码里。

再次强调：

递推时要注意，上不越界，下不越界，条件满足才能转移，小心转移到不合法或不应该转移去的位置。

#include<bits/stdc++.h>
using namespace std;

int d,g,f[155][155],ans;
struct rubbish{
	int t,f,h;
	bool operator < (rubbish x){
		return t<x.t;
	}	
}a[105];

int main()
{
	freopen("input.in","r",stdin);
	cin>>d>>g;
	for(int i=1;i<=g;i++)cin>>a[i].t>>a[i].f>>a[i].h;
	sort(a+1,a+1+g);  
	memset(f,-1,sizeof(f));
	f[0][0]=10;
	for(int i=1;i<=g;i++)
	{
		bool out=0,died=1;
		for(int j=0;j<=d;j++)
		{
			if(j-a[i].h>=0 && f[i-1][j-a[i].h]-(a[i].t-a[i-1].t)>=0)f[i][j]=f[i-1][j-a[i].h]-(a[i].t-a[i-1].t);
			if(f[i-1][j]-(a[i].t-a[i-1].t)>=0)f[i][j]=max(f[i][j],f[i-1][j]-(a[i].t-a[i-1].t)+a[i].f);
			if(j==d)if(f[i][j]>=0)out=1;
			if(f[i][j]>=0)died=0;
		}
		if(out){ans=a[i].t;break;}
		else if(died)
		{
			int maxn=0;
			for(int j=0;j<=d;j++)if(f[i-1][j]>maxn)maxn=f[i-1][j];
			ans=a[i-1].t+maxn;
			break;
		}
	}
	if(!ans)
	{
		int j;
		for(j=0;j<=100;j++)if(f[g][j]>=0)break;
		ans=a[g].t+f[g][j];
	}
	cout<<ans<<endl;
	return 0;
}