洛谷-P1833 樱花（混合背包模板）

题目背景

《爱与愁的故事第四弹·plant》第一章。

题目描述

爱与愁大神后院里种了n棵樱花树，每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看Ai遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

输入格式

共n+1行：

第1行：三个数：现在时间Ts（几点：几分），去上学的时间Te（几点：几分），爱与愁大神院子里有几棵樱花树n。

第2行~第n+1行：每行三个数：看完第i棵树的耗费时间Ti，第i棵树的美学值Ci，看第i棵树的次数Pi（Pi=0表示无数次，Pi是其他数字表示最多可看的次数Pi）。

输出格式

只有一个整数，表示最大美学值。

输入输出样例

输入样例

6:50 7:00 3
2 1 0
3 3 1
4 5 4

输出样例

11

说明/提示

100%数据：Te-Ts ≤ 1000，n ≤ 10000

样例解释：赏第一棵樱花树一次，赏第三棵樱花树2次

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff;

string time1, time2;
int totalTime = 1005, n = 10000;
vector<int> d(totalTime, 0);

int getTime(string & s1, string & s2)
{
    int pos1 = find(s1.begin(), s1.end(), ':') - s1.begin();
    int pos2 = find(s2.begin(), s2.end(), ':') - s2.begin();

    return (stoi(s2.substr(0, pos2)) - stoi(s1.substr(0, pos1))) * 60 + 
        stoi(s2.substr(pos2 + 1)) - stoi(s1.substr(pos1 + 1));
}

void oneZeroPack(int cost, int value)
{
    for (int i = totalTime; i >= cost; --i) {
        d[i] = max(d[i], d[i - cost] + value);
    }
}

void completePack(int cost, int value)
{
    for (int i = cost; i <= totalTime; ++i) {
        d[i] = max(d[i], d[i - cost] + value);
    }
}

void multiPack(int cost, int value, int frequency)
{
    if (cost * frequency >= totalTime) {
        completePack(cost, value);
        return;
    }
    int k = 1;
    while (k < frequency) {
        oneZeroPack(k * cost, k * value);
        frequency -= k;
        k = k * 2;
    }
    oneZeroPack(cost * frequency, value * frequency);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> time1 >> time2 >> n;
    totalTime = getTime(time1, time2);

    for (int i = 0; i < n; ++i) {
        int cost, value, frequency;
        cin >> cost >> value >> frequency;
        if (frequency == 0) completePack(cost, value);
        else if (frequency == 1) oneZeroPack(cost, value);
        else multiPack(cost, value, frequency);
    }
    cout << d[totalTime] << endl;

    return 0;
}