洛谷题单指南-动态规划2-P1833 樱花

原题链接：https://www.luogu.com.cn/problem/P1833

题意解读：在有限的时间内，看n株樱花树，第i株樱花树可以看pi次，看每株樱花树耗费时间ti，看每株樱花树一次美学值ci，求最多能看到多少美学值。

解题思路：

本题实质是一个混合背包问题（pi>0是多重背包，pi=0是完全背包）：

背包容量：总时间，可以根据时间的终点和起点计算；

物品：樱花，n种

每种物品体积：看每株樱花耗费的时间ti

每种物品价值：看每株樱花增加的美学值ci

每种物品数量：第i株樱花树可以看pi次

先从最朴素的方法开始思考，再进行优化：

朴素版：

设t[i]表示第i株樱花耗费时间，c[i]表示第i株樱花美学值，p[i]表示第i株樱花可看次数

设dp[i][j]表示在时间j之内看前i株樱花的最大美学值，

对于第i株，可以看0,2,3....k次，

p[i]=0时代表无限次，用完全背包，所以条件为j - k * t[i] >= 0

p[i]>0只能看有限次，用多重背包，条件为k < p[i]&& j - k * t[i] >= 0 

状态转移都是dp[i][j] = max(dp[i - 1][j - 0 * t[i]] + 0 * c[i], dp[i-1][j-1 * t[i]] + 1 * c[i]), dp[i-1][j-2 * t[i]] + 2 * c[i]) , ...... , dp[i-1][j-k * t[i]] + k * c[i])

需要三重循环，i最大10000，j最大1000，k最大100，显然会超时，先得部分分再说！

100分代码(样例有点水)：

#include <bits/stdc++.h>
using namespace std;

const int N = 10005, M = 1005, P = 105;
int p[N]; //每株樱花可看次数
int c[N]; //每株樱花美学值
int t[N]; //每株樱花耗费时间
int dp[N][M]; //dp[i][j]表示在时间j之内看前i株樱花的最大美学值
int T; //最大时间限制
int n;

int main()
{
    int h1, m1, h2, m2;
    scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);
    T = h2 * 60 + m2 - (h1 * 60 + m1);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &t[i], &c[i], &p[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= T; j++)
        {
            if(p[i]== 0)
            {
                for(int k = 0; j >= k * t[i]; k++)
                {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k * t[i]] + k * c[i]);
                }
            }
            else
            {
                for(int k = 0; k <= p[i] && j >= k * t[i]; k++)
                {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k * t[i]] + k * c[i]);
                }
            }
        }
    }
    cout << dp[n][T];

    return 0;
}

100分代码-一维：

#include <bits/stdc++.h>
using namespace std;

const int N = 10005, M = 1005, P = 105;
int p[N]; //每株樱花可看次数
int c[N]; //每株樱花美学值
int t[N]; //每株樱花耗费时间
int dp[M]; //dp[j]表示在时间j之内看的最大美学值
int T; //最大时间限制
int n;

int main()
{
    int h1, m1, h2, m2;
    scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);
    T = h2 * 60 + m2 - (h1 * 60 + m1);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &t[i], &c[i], &p[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        if(p[i] == 0) //完全背包
        {
            for(int j = t[i]; j <= T; j++) //正序遍历
            {
                dp[j] = max(dp[j], dp[j - t[i]] + c[i]);
            }
        }
        else //多重背包
        {
            for(int j = T; j >= 0; j--) //逆序遍历
            {
                 for(int k = 0; k <= p[i] && j >= k * t[i]; k++)
                 {
                    dp[j] = max(dp[j], dp[j - k * t[i]] + k * c[i]);
                 }
            }
        }
    }
    cout << dp[T];

    return 0;
}

二进制优化：

对于多重背包或者完全背包，可以用二进制优化。

二进制优化的原理是倍增思想，对于第i个物品有p个，则可以把该物品拆分成多个物品，每个物品是原物品的1/2/4/8....个组合而成。

因为对于一个整数p以内的数，总可以由1/2/4/8....2^i/p-2^i中的若干项相加得到，如此把一个物品的p个拆分成多个物品之后，就可以通过01背包问题来解决多重、完全背包问题，因为所有选法一定会覆盖每个物品选0个、1个、2个。。。。。k个的情况。

100分代码-二进制优化：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, M = 1005; //注意一个樱花最多可以看100次，大概可以拆分成Log100≈7个，N开到100000比较保险
int p[N]; //每株樱花可看次数
int c[N]; //每株樱花美学值
int t[N]; //每株樱花耗费时间
int cnt;
int dp[M]; //dp[j]表示在时间j之内看的最大美学值
int T; //最大时间限制
int n;

int main()
{
    int h1, m1, h2, m2;
    scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);
    T = h2 * 60 + m2 - (h1 * 60 + m1);
    int tx, cx, px;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &tx, &cx, &px);
        if(px == 0) px = T / tx; //如果是无限次，设置为最大可看次数：总时间 / 耗费时间
        int num = 1;
        while(px >= num) //将第i个物品拆分为1/2/4/8....个
        {
            cnt++;
            t[cnt] = tx * num;
            c[cnt] = cx * num;
            p[cnt] = num;
            px -= num;
            num *= 2;
        }
        if(px)
        {
            cnt++;
            t[cnt] = tx * px;
            c[cnt] = cx * px;
            p[cnt] = px;
        }
    }

    for(int i = 1; i <= cnt; i++) //01背包
    {
        for(int j = T; j >= t[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - t[i]] + c[i]);
        }
    }
    printf("%d", dp[T]);

    return 0;
}