蚂蚁的难题(三)
时间限制:2000 ms | 内存限制:65535 KB
难度:4
-
描述
-
蚂蚁终于把尽可能多的食材都搬回家了,现在开始了大厨计划。
已知一共有 n 件食材,每件食材有一个美味度 Ai 和新鲜度 Bi , 如果蚂蚁在第t时刻将第i样食材烹饪成功,则得到Ai-t*Bi 的美味指数,当然,用第i件食材做饭要花去 Ci 的时间。
众所周知,蚂蚁的厨艺不怎么样,所以他需要你设计做饭方案使得在时间 T 内完成的美味指数最大。
-
输入
- 有多组测试数据。
第一行是两个正整数,表示蚂蚁的做饭时间T和食材个数n。(n<=50, 1<=T<=100000)。
接下来n行,每行有三个数,Ai,Bi,Ci。分别代表美味度、新鲜度和用该食材做饭花费的时间。(0<Ai,Bi,Ci<=100000).
-
输出
- 输出一个数字,表示最大美味指数
-
样例输入
-
6 1
200 5 1
-
样例输出
-
195
-
来源
- 蚂蚁系列
-
上传者
- ACM_李如兵
还是对背包理解不够透啊!!!
如果没有B[i]这个属性的话就是明显的01背包问题。
现在考虑相邻的两个物品x,y.假设现在已经耗费p的时间,那么分别列出先做x,y的代价:
A[x]-(p+C[x])*B[x]+A[y]-(p+C[x]+C[y])*B[y] ①
A[y]-(p+C[y])*B[y]+A[x]-(p+C[y]+C[x])*B[x] ②
对这两个式子化简,得到 ①>② 的条件是 c[x]*b[y]<c[y]*b[x].
发现只要满足这个条件的物品对(x,y),x在y前的代价永远更优。
因此可以根据这个条件进行排序,之后就是简单的01背包了。
ac代码
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct s
{
long long a,b,c;
}food[1000005];
bool cmp(s A,s B)
{
return (long long)A.c*(long long)B.b<(long long)B.c*(long long)A.b;
}
long long dp[100015];
int main()
{
long long t;
int n;
while(scanf("%lld%d",&t,&n)!=EOF)
{
int i,j;
long long sum=0,sumt=0,ans=-1;
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
{
scanf("%lld%lld%lld",&food[i].a,&food[i].b,&food[i].c);
}
sort(food,food+n,cmp);
for(i=0;i<n;i++)
{
for(j=t;j>=food[i].c;j--)
{
dp[j]=max(dp[j],dp[j-food[i].c]+food[i].a-food[i].b*j);
}
}
for(i=0;i<t;i++)
if(ans<dp[i])
ans=dp[i];
printf("%lld\n",ans);
}
}
蚂蚁的难题(三)
时间限制:2000 ms | 内存限制:65535 KB
难度:4
蚂蚁终于把尽可能多的食材都搬回家了,现在开始了大厨计划。
已知一共有 n 件食材,每件食材有一个美味度 Ai 和新鲜度 Bi , 如果蚂蚁在第t时刻将第i样食材烹饪成功,则得到Ai-t*Bi 的美味指数,当然,用第i件食材做饭要花去 Ci 的时间。
众所周知,蚂蚁的厨艺不怎么样,所以他需要你设计做饭方案使得在时间 T 内完成的美味指数最大。
- 输入
- 有多组测试数据。
第一行是两个正整数,表示蚂蚁的做饭时间T和食材个数n。(n<=50, 1<=T<=100000)。
接下来n行,每行有三个数,Ai,Bi,Ci。分别代表美味度、新鲜度和用该食材做饭花费的时间。(0<Ai,Bi,Ci<=100000). - 输出
- 输出一个数字,表示最大美味指数
- 样例输入
-
6 1 200 5 1
- 样例输出
-
195
- 来源
- 蚂蚁系列
- 上传者
- ACM_李如兵
还是对背包理解不够透啊!!!
如果没有B[i]这个属性的话就是明显的01背包问题。
现在考虑相邻的两个物品x,y.假设现在已经耗费p的时间,那么分别列出先做x,y的代价:
A[x]-(p+C[x])*B[x]+A[y]-(p+C[x]+C[y])*B[y] ①
A[y]-(p+C[y])*B[y]+A[x]-(p+C[y]+C[x])*B[x] ②
对这两个式子化简,得到 ①>② 的条件是 c[x]*b[y]<c[y]*b[x].
发现只要满足这个条件的物品对(x,y),x在y前的代价永远更优。
因此可以根据这个条件进行排序,之后就是简单的01背包了。
ac代码
#include<stdio.h> #include<stdlib.h> #include<algorithm> #include<string.h> using namespace std; struct s { long long a,b,c; }food[1000005]; bool cmp(s A,s B) { return (long long)A.c*(long long)B.b<(long long)B.c*(long long)A.b; } long long dp[100015]; int main() { long long t; int n; while(scanf("%lld%d",&t,&n)!=EOF) { int i,j; long long sum=0,sumt=0,ans=-1; memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) { scanf("%lld%lld%lld",&food[i].a,&food[i].b,&food[i].c); } sort(food,food+n,cmp); for(i=0;i<n;i++) { for(j=t;j>=food[i].c;j--) { dp[j]=max(dp[j],dp[j-food[i].c]+food[i].a-food[i].b*j); } } for(i=0;i<t;i++) if(ans<dp[i]) ans=dp[i]; printf("%lld\n",ans); } }