为什么我二维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;
}
(悬关)