[luogu] p2854 Cow Roller Coaster 二维背包问题

前言

果然一遇到背包的这种问题,我就有一点束手无策hh 传送门 :

思路

题目给我们一下几个量 : L ( 区 间 长 度 ) , N ( 输 入 组 数 ) , B ( 最 大 费 用 ) L(区间长度),N(输入组数),B(最大费用) L(区间长度),N(输入组数),B(最大费用)

题目要求 : 需要在满足装满体积的情况下,不超过最大费用 的最大价值

显然对于这种题,我们一般都是小区间 d p dp dp到大区间

所以状态表示 : f [ i ] [ j ] f[i][j] f[i][j]表示能覆盖[0~i]的区间,且费用不超过j的最大价值

因此状态转移按照 01 01 01背包来推算的话,应该是

f [ i . x + i . b ] [ j ] = m a x ( f [ i . x + i . b ] [ k ] , f [ i . x ] [ k − i . v ] + i . w ) f[i.x + i.b][j] =max( f[i.x+i.b][k],f[i.x][k-i.v]+i.w ) f[i.x+i.b][j]=max(f[i.x+i.b][k],f[i.x][k−i.v]+i.w)

• 如果不选这个点那么 就从 f [ i . x + i . b ] [ k ] f[i.x+i.b][k] f[i.x+i.b][k]转移过来
• 否则选这个点,那么上一个点转移过来 f [ i . x ] [ k − i . v ] + i . w f[i.x][k-i.v]+i.w f[i.x][k−i.v]+i.w

当然这个是在 [0~i]之间有通路的情况下才可以转移

为了方便 d p dp dp 我们需要按照起点排序一下

CODE

struct node
{
	int a,b,v,w;
}num[N];

int f[M][M];
int l,m,n,ans;

bool cmp(node x,node y)
{
	return x.a  >l>>n>>m;
	for(int i=1;i>num[i].a>>num[i].b>>num[i].w>>num[i].v;
	//起点 长度 价值 费用

	sort(num+1,num+1+n,cmp);
	
	for(int i=1;i=num[i].v;k--)//枚举费用
		{
			
			if(num[i].a !=0 && f[num[i].a][k-num[i].v]==0) 
			continue;
			//只有在 起点不为0 
			f[num[i].a+num[i].b][k] = max(
			f[num[i].a+num[i].b][k],
			f[num[i].a][k-num[i].v]+num[i].w
			);
		}
	}

	for(int i=1;i