为什么只有第二个DP才能算正确答案?
查看原帖
为什么只有第二个DP才能算正确答案?
666682
songsonghui楼主2022/3/14 18:21
//	ci:某个石头所需体力,vi:某个石头的体积 
	for(int i = 1;i<=n;i++){//前n个石头 
		for(int j =0;j<=c;j++){//体力 0-c;c:现有体力 
			if(ci[i]<=j)
				dp[j] = max(dp[j],dp[j-ci[i]] + vi[i]);
		}
	}		
	
	for(int i = 1;i<=n;i++){//前n个石头  
		for(int j =c;j>=ci[i];j--){//体力 c-ci[i];c:现有体力 
				dp[j] = max(dp[j],dp[j-ci[i]] + vi[i]);
		}
	}
2022/3/14 18:21
加载中...