admin 管理员组文章数量: 887032
面包
面包
(cheese.pas/c/cpp)
【问题描述】
Farmer John 有 N 种不同类型的面包(编号 1~N),每种面包的数量无限多。 Farmer John
想用这些面包堆成一个高度不超过 T 的面包塔。第 i 种面包的价值是 V_i,高度是 H_i,而且
高度是 5 的倍数。已知一个常量 K,如果高度≥K,我们称它为“大面包”,大面包会把堆在
它下面的所有面包都压扁(即使下面同样有大面包)。面包被压扁后价值不会改变,但高度
变成了原来的 4/5。由于所有面包原来高度都是 5 的倍数,所以压扁后的高度还是整数。某
块面包被压扁一次后不会再被压扁第二次,也就是说每块面包要么被压扁要么不被压扁。现
在的问题是: Farmer John 堆成一个高度不超过 T(1≤T≤l000)的面包塔,能获得最大的价值
是多少?
例如: T=53, K=25。以下有三种不同类型的面包,数量无限:
Type Value Height
1 100 25
2 20 5
3 40 10
FJ 能够堆出下面的面包塔:
Type Height Value
Top -> [1] 25 100
[2] 4 20 <一被第[1]块面包压扁了
[3] 8 40 <一被第[1]块面包压扁了
[3] 8 40 <一被第[1]块面包压扁了
Bottom -> [3] 8 40 <一被第[1]块面包压扁了
由于最上层的面包高度是 25≥K,所以把它下面所有的面包压扁,面包塔总高度是:
25+4+8+8+8 刚好不超过 T,所以是合法的,面包塔的总价值是: 100+20+40+40+40=240。这
也是最优方案:
【输入格式】
第 1 行:三个整数: N, T, K。
第 2~N+1 行:第 i+1 行有两个整数: v_i、 H_i,表示第 i 种面包的信息。
【输出格式】
一行:能堆出来的最大价值。
【输入样例】
3 53 25
100 25
20 5
40 10
【输出样例】
240
【数据规模】
对于 30%的数据:1≤N≤15; 1≤T≤100;
对于 70%的数据:1≤N≤70; 1≤T≤500;
对于 100%的数据:1≤N≤100; 1≤T≤1,000; 1≤V_i≤1,000,000; 5≤H_i≤T; 1≤K≤T;
这题是个完全背包,这是毋庸置疑的,但是因为有4/5,整个题目的难度就提升了。
此题的做法是先将高度比k小的面包取出,做一次完全背包。将其记录为ans1。
然后将所有面包高度的4/5取出,做一遍完全背包,最后再在上面取出高度比k大的
面包,再做再顶部。将其记录为ans2。
输出max(ans1,ans2)即可。
#include<bits/stdc++.h>
#define C c=getchar()
using namespace std;
int i,j,k,n,m,tot,ans,t;
int f[1005],h[105],v[105];
int read(){char c;int x;while(C,c<'0'||c>'9');x=c-'0';while(C,c>='0'&&c<='9') x=x*10+c-'0';return x;
}
int maxn(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int main()
{freopen("cheese.in","r",stdin);freopen("cheese.out","w",stdout);n=read();t=read();k=read();for(int i=1;i<=n;i++){v[i]=read(); h[i]=read();}for(int i=1;i<=n;i++)if(h[i]<k) for(int j=h[i];j<=t;j++) f[j]=maxn(f[j],f[j-h[i]]+v[i]);for(int i=0;i<=t;i++) ans=maxn(ans,f[i]);for(int i=1;i<=n;i++)for(int j=h[i]*4/5;j<=t;j++) f[j]=maxn(f[j],f[j-h[i]*4/5]+v[i]);for(int i=1;i<=n;i++)if(h[i]>=k) for(int j=h[i];j<=t;j++) ans=maxn(ans,f[j-h[i]]+v[i]);printf("%d",ans);return 0;
}
本文标签: 面包
版权声明:本文标题:面包 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1686976194h52299.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论