滚动数组二维背包,70ptsWA求调
查看原帖
滚动数组二维背包,70ptsWA求调
372336
一个句号楼主2023/8/23 14:45
#include<iostream>
using namespace std;
int h,t,n;
int hs[60],ts[60],ks[60];
int dp[405][305];
//二位费用背包:滚动数组板子
int main(){
	cin>>h>>t;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>hs[i]>>ts[i]>>ks[i];
	for(int i=1;i<=n;i++){//下面两个维度都是逆序,01背包
		for(int j=h;j>=hs[i];j--){
			for(int k=t;k>=ts[i];k--){
				dp[j][k]=max(dp[j][k],dp[j-hs[i]][k-ts[i]]+ks[i]);
			}
		}
	}
	cout<<dp[h][t];
	return 0;
}
2023/8/23 14:45
加载中...