赞
踩
FJ要建一个奶酪塔,高度最大为T。他有N种奶酪。第i种奶酪的高度为Hi(一定是5的倍数),价值为Vi。一块高度Hi>=K的奶酪被称为大奶酪,一个奶酪如果在它上方有大奶酪(如果有多块就只算一次),它的高度Hi就会变成原来的4/5.。FJ想让他的奶酪塔价值和最大。请你求出这个最大值。
第一行三个数N,T,K,意义如上所述。 接下来n行,每行两个数V_i,h_i(注意顺序)
奶酪塔的最大价值
3 53 25
100 25
20 5
40 10
240
(1)用数组f记录体积未被压缩时的最大价值
(2)用数组ff记录体积被压缩后的最大价值
(3)for循环枚举去掉最上面奶酪体积的最大价值ff[j]加上最上面的奶酪价值v[i]
(4)比较压缩前后的最大价值(如果不存在大奶酪,则ff数组均为0,输出压缩前最大价值;反之,压缩后最大价值必然大于等于压缩前最大价值)
#include <bits/stdc++.h> #define M(a, b) memset(a, b, sizeof(a)) #define INF 0x3f3f3f3f #define MOD 10000007 using namespace std; inline void read(int &x){ char ch=getchar(),c=ch; x=0; while(ch<'0' || ch>'9'){ c=ch; ch=getchar(); } while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } if(c=='-')x=-x; } int n,T,k,ans,i,j; int f[2000],v[1000],h[1000]; int main(){ read(n),read(T),read(k); for(i=1;i<=n;i++) { read(v[i]),read(h[i]); for(j=h[i];j<=T*5/4;j++)f[j]=max(f[j],f[j-h[i]]+v[i]); } ans=f[T]; for(i=1;i<=n;i++) if(h[i]>=k)ans=max(ans,f[(T-h[i])*5/4]+v[i]); printf("%d\n",ans); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。