关于这道题,请问一下这两份代码有什么不同。 90pts,WA一个点的代码:
#include<bits/stdc++.h>
using namespace std;
int dp[50005],n,x,y,z,cnt=1,ans=-1;
struct node{
int h,a;
}a[4005];
bool cmp(node x,node y){
return x.a<y.a;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
for(int j=1;j<=z;j++){
a[cnt++]=(node){x,y};
}
}
sort(a+1,a+cnt,cmp);
for(int i=1;i<cnt;i++){
for(int j=a[i].a;j>=a[i].h;j--){
dp[j]=max(dp[j],dp[j-a[i].h]+a[i].h);
ans=max(ans,dp[j]);
}
}
printf("%d",ans);
return 0;
}
100pts代码:
#include<bits/stdc++.h>
using namespace std;
int dp[50005],n,cnt=1,ans=0;
struct node{
int h,a;
}A[5000];
bool cmp(node a,node b){
return a.a<b.a;
}
int main(){
scanf("%d",&n);
for(int i=1,h,a,c;i<=n;i++){
scanf("%d%d%d",&h,&a,&c);
for(int j=1;j<=c;j++){
A[cnt++]=(node){h,a};
}
}
sort(A+1,A+cnt,cmp);
for(int i=1;i<cnt;i++){
for(int j=A[i].a;j>=A[i].h;j--){
dp[j]=max(dp[j],dp[j-A[i].h]+A[i].h);
ans=max(ans,dp[j]);
}
}
printf("%d",ans);
return 0;
}
蒟蒻半天没看出差别,求求大佬帮帮忙