题意:
要建一个奶酪塔, 高度最大为 T.
有 N 块奶酪. 第 i 块高度为 Hi(一定是 5 的倍数), 价值为 Vi.
一块高度 >=K 的奶酪被称为大奶酪, 一个奶酪如果在它上方有大奶酪 (多块只算一次),
它的高度就会变成原来的 4/5. 求最大奶酪价值
首先, 要想得到最大价值的奶酪, 要不就不要 >=k 的, 要不就要一个, 放在最顶上!(贪心最优!)
所以, 对于不要的, 直接完全背包 dp 即可,
因为 $(j-w[i])\to\frac{4}{5}h$
所以 $\frac{5}{4}(j-w[i])\to h$
注意转移
最后取 max
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<cctype>
- #include<algorithm>
- using namespace std;
- #define olinr return
- #define _ 0
- #define love_nmr 0
- #define DB double
- inline int read()
- {
- int x=0,f=1;
- char ch=getchar();
- while(!isdigit(ch))
- {
- if(ch=='-')
- f=-f;
- ch=getchar();
- }
- while(isdigit(ch))
- {
- x=(x<<1)+(x<<3)+(ch^48);
- ch=getchar();
- }
- return x*f;
- }
- inline void put(int x)
- {
- if(x<0)
- {
- x=-x;
- putchar('-');
- }
- if(x>9)
- put(x/10);
- putchar(x%10+'0');
- }
- struct node
- {
- int v;
- int w;
- }a[205];
- int n;
- int t;
- int k;
- int f[1050];
- int main()
- {
- n=read();
- t=read();
- k=read();
- for(int i=1;i<=n;i++)
- {
- a[i].v=read();
- a[i].w=read();
- }
- for(int i=1;i<=n;i++)
- for(int j=a[i].w;j<=t*5/4;j++)
- {
- f[j]=max(f[j],f[j-a[i].w]+a[i].v);
- }
- int ans=0;
- for(int i=1;i<=n;i++)
- if(a[i].w>=k)
- ans=max(ans,f[(t-a[i].w)*5/4]+a[i].v);
- put(max(ans,f[t]));
- olinr ~~(0^_^0)+love_nmr;
- }
来源: http://www.bubuko.com/infodetail-2752812.html