求救——美食大赛

常规
1 
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+5;
struct node{
	int a,b,c;
}a[maxn];
int n;
long long dp[maxn];
bool cmp(node a,node b){
	return a.b*a.c<b.b*b.c;
}
int t;
long long ans=-1;
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].a;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].b;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].c;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=t;j>=a[i].c;j--){ //逆序 
			dp[j]=max(dp[j],dp[j-a[i].c]+a[i].a-j*a[i].b);
			ans=max(ans,dp[j]);
			//cout<<dp[i-1][j]<<" ";
		}
		//cout<<"\n"; 
	}
	return 0;
}

wa30
样例
{
in：
5611 34
61302 23769 76251 33365 71919 91361 65553 48998 73771 25981 66005 23747 34553 45091 73977 23053 96341 95741 23265 42363 35079 17601 42033 42272 91459 26089 15651 90332 91821 36109 40370 57633 4551 33352
108 183 228 47 239 45 142 44 111 213 65 249 165 269 198 213 246 190 140 109 277 246 10 197 46 261 140 47 132 231 294 39 155 159
112 261 178 194 16 27 238 27 81 78 29 245 106 152 248 225 198 244 91 62 141 197 130 287 151 118 275 64 152 13 75 39 240 190
out：
601925
}

5 个赞
2

ans应该=0

3 个赞
3

谢谢

3 个赞
4

a,b,c开long long

3 个赞
5

排序也排错了

3 个赞
6

变量名改一下
太多重名了 :rage:

3 个赞
7

sorry，删的时候误删了

3 个赞
8

好像还是不行，wa50
不过好多了

3 个赞
9

改一下格式

3 个赞
10

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
struct node{
long long a,b,c;
}a[maxn];
int n;
long long dp[maxn];
bool cmp(node x,node y){
return x.bx.c<y.by.c;
}
int t;
long long ans=0;
int main(){
cin>>t>>n;
for(int i=1;i<=n;i++){
cin>>a[i].a;
}
for(int i=1;i<=n;i++){
cin>>a[i].b;
}
for(int i=1;i<=n;i++){
cin>>a[i].c;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=t;j>=a[i].c;j–){ //逆序
dp[j]=max(dp[j],dp[j-a[i].c]+a[i].a-j*a[i].b);
ans=max(ans,dp[j]);
//cout<<dp[i-1][j]<<" “;
}
//cout<<”\n";
}
cout<<ans;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=t;j++){
// cout<<dp[j]<<" ";
// }
// cout<<endl;
// }
return 0;
}

3 个赞
11

排序还是错的呀

2 个赞
12

问一下，怎么排

2 个赞
13

这还要问
老师不是讲了吗

2 个赞
14

是要加一个非吗


bool cmp(node x,node y){
	return !x.b*x.c<y.b*y.c;
}
2 个赞
15

return x.b*y.c>y.b*x.c;

2 个赞
16

然后把a,b,c改long long就能AC了

2 个赞
17 
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long a,b,c;
}food[100005];
long long dp[100005];
bool cmp(node x,node y){
	return x.b*y.c>y.b*x.c;
}
int main()
{
	long long t,n,tt,maxx=0;
	cin>>t>>n;
	for(int i=0;i<n;i++)
		cin>>food[i].a;
	for(int i=0;i<n;i++)
		cin>>food[i].b;
	for(int i=0;i<n;i++)
		cin>>food[i].c;
	sort(food,food+n,cmp);
	dp[0]=0;
	for(int i=0;i<n;i++)
		for(int j=t;j>=food[i].c;j--)
		{
			dp[j]=max(dp[j],dp[j-food[i].c]+(food[i].a-j*food[i].b));
			maxx=max(maxx,dp[j]);
			
		}
	cout<<maxx;
	return 0;
}
2 个赞
18

谢谢

2 个赞