只能一维滚动?
查看原帖
只能一维滚动?
928895
NOBenRen楼主2024/7/15 19:53

为什么我二维20,一维AC 2维:

#include <bits/stdc++.h>
using namespace std;
long long x,y,m,n,a[105],w[105],v[105],ans[105][5005],h;
int main(){
	cin>>x>>y>>m>>n;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]*=y/x;
	for(int i=1;i<=m;i++)cin>>w[i]>>v[i],w[i]=a[w[i]];
	cin>>h;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=h;j++){
			if(w[i]>j)ans[i][j]=ans[i-1][j];
			else ans[i][j]=max(ans[i-1][j],ans[i-1][j-w[i]]+v[i]);
		}
	cout<<ans[n][h];
	return 0;
}

一维:

#include <bits/stdc++.h>
using namespace std;
long long x,y,m,n,a[105],w[105],v[105],ans[5005],h;
int main(){
	cin>>x>>y>>m>>n;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]*=y/x;
	for(int i=1;i<=m;i++)cin>>w[i]>>v[i],w[i]=a[w[i]];
	cin>>h;
	for(int i=1;i<=m;i++)
		for(int j=h;j>=w[i];j--)
			ans[j]=max(ans[j],ans[j-w[i]]+v[i]);
	cout<<ans[h];
	return 0;
}

(悬关)

2024/7/15 19:53
加载中...