求助
  • 板块P6326 Shopping
  • 楼主Mini_PEKKA
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/19 14:35
  • 上次更新2024/6/19 19:18:32
查看原帖
求助
680197
Mini_PEKKA楼主2024/6/19 14:35

以下两份代码

AC:

int l=d[u]-1;

rep(j,c[u],m){
	f[i][j]=f[i+1][j-c[u]]+w[u];
}
for(int j=1;j<=l;l-=j,j<<=1){
	rep(k,c[u]*j,m){
		g[i][k]=max(f[i][k],f[i][k-c[u]*j]+w[u]*j);
	}
	rep(k,c[u]*j,m){
		f[i][k]=g[i][k];
	}
}
rep(j,c[u]*l,m){
	g[i][j]=max(f[i][j],f[i][j-c[u]*l]+w[u]*l);
}
rep(j,c[u]*l,m){
	f[i][j]=g[i][j];
}

WA:

int l=d[u];
for(int j=1;j<=l;l-=j,j<<=1){
	rep(k,c[u]*j,m){
		f[i][k]=max(f[i][k],f[i+1][k-c[u]*j]+w[u]*j);
	}
}
if(l){
	rep(j,c[u]*l,m){
		f[i][j]=max(f[i][j],f[i+1][j-c[u]*l]+w[u]*l);
	}
}

都强制选了一个物品,为什么结果不同?

2024/6/19 14:35
加载中...