[题目描述:]
爱与愁大神后院里种了 n 棵樱花树, 每棵都有美学值 Ci. 爱与愁大神在每天上学前都会来赏花. 爱与愁大神可是生物学霸, 他懂得如何欣赏樱花: 一种樱花树看一遍过, 一种樱花树最多看 Ai 遍, 一种樱花树可以看无数遍. 但是看每棵樱花树都有一定的时间 Ti. 爱与愁大神离去上学的时间只剩下一小会儿了. 求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时 (或提早) 去上学.
[输入格式:]
共 n+1 行:
第 1 行: 三个数: 现在时间 Ts(几点: 几分), 去上学的时间 Te(几点: 几分), 爱与愁大神院子里有几棵樱花树 n.
第 2 行~ 第 n+1 行: 每行三个数: 看完第 i 棵树的耗费时间 Ti, 第 i 棵树的美学值 Ci, 看第 i 棵树的次数 Pi(Pi=0 表示无数次, Pi 是其他数字表示最多可看的次数 Pi).
[输出格式:]
只有一个整数, 表示最大美学值.
输入样例 #1:
- 6:50 7:00 3
- 2 1 0
- 3 3 1
- 4 5 4
输出样例 #1:
11
输入输出样例
[算法分析:]
01 背包可以看做是只有一件物品的多重背包, 所以可将三类背包问题化为两类:
多重背包
完全背包
但多重背包直接做时间复杂度太大, 所以需要二进制优化, 此时如何处理完全背包问题?
可以将完全背包的数量看做一个比较大, 而数组中也存的开的数, 比如 9999, 然后当做多重背包来做.
[代码:]
- //P1833 樱花
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int MAXN = 1000000 + 1;
- const int INF = 9999;
- int n, T;
- int t[MAXN], c[MAXN], p[MAXN];
- int a[MAXN], b[MAXN], f[MAXN];
- struct Time {
- int h, min;
- }s, e;
- inline int read() {
- int x=0, f=1; char ch=getchar();
- while(ch<'0' || ch>'9') {
- if(ch == '-') f = -1;
- ch = getchar();
- }
- while(ch>='0' && ch<='9')
- x=(x<<3) + (x<<1) + ch-48, ch = getchar();
- return x * f;
- }
- int main() {
- s.h = read(), s.min = read();
- e.h = read(), e.min = read();
- n = read();
- T = e.min - s.min + (e.h - s.h) * 60;
- int cnt = 0;
- for(int i=1; i<=n; ++i) {
- t[i] = read(), c[i] = read(), p[i] = read();
- if(!p[i]) p[i] = INF;
- int s = 1;
- while(p[i]> s) {
- a[++cnt] = t[i] * s;
- b[cnt] = c[i] * s;
- p[i] -= s;
- s <<= 1;
- }
- if(p[i]) {
- a[++cnt] = t[i] * p[i];
- b[cnt] = c[i] * p[i];
- }
- }
- for(int i=1; i<=cnt; ++i)
- for(int j=T; j>=a[i]; --j)
- f[j] = max(f[j], f[j - a[i]] + b[i]);
- printf("%d\n", f[T]);
- }
来源: http://www.bubuko.com/infodetail-2610363.html