警示后人,01背包
  • 板块P1802 5 倍经验日
  • 楼主stmo
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/13 20:45
  • 上次更新2023/12/14 07:54:08
查看原帖
警示后人,01背包
1090758
stmo楼主2023/12/13 20:45

因为写背包问题的时候我们通常熟悉这样写,

for(int i=1;i<=n;i++){
	for(int j=x;j>=0;j--)
		f[j]=f[j]+shu[i];
		if(j>=nd[i])
		f[j]=max(f[j]+shu[i],f[j-nd[i]]+win[i]);
		
	}
}

但是这样肯定错了,应为你的if条件如果成立,那么你的f[j]已经发生了改变,所以必然出错, 所以一定要把输了的情况放后面

for(int i=1;i<=n;i++){
	for(int j=x;j>=0;j--){
		if(j>=nd[i])
			f[j]=max(f[j]+shu[i],f[j-nd[i]]+win[i]);
		else f[j]+=shu[i];
	}
}

对了,记得要将j>=0应为即使没有解药,一直输也是有加经验的

2023/12/13 20:45
加载中...