更好的阅读体验

题目概述

题目描述

魔兽争霸3中，战略资源的采集通过使用农民、苦工、小精灵以及寺僧来进行。

在魔兽争霸4的开发中，玻璃渣觉得这种模式太过单一，于是他们想添加更多的单位来使采集的模式更加丰富。

在新的模式中，玩家可以建造更多种类的“苦工”，不同的“苦工”的工作效率不同，同时，建造不同的“苦工”所需要的资源也是不一样的。

玻璃渣出品的游戏以追求平衡著称，所以为了测试这种新的模式的平衡性，他们设计了一套检测的方法：在各种族的起始资源相同时，测量达到某一资源数量的时间，如果相同则可以认为设计是平衡的。

他们将数据给你，希望你能测试出设计是否平衡。

输入格式

第一行三个数，$N, M, T$, 表示苦工的种类、开始时拥有的资源数量以及需要达到的资源的数量。

接下来$N$行，每行$2$个数$A, B$, 表示生产这种苦工所需要的资源，以及这个苦工的效率，效率即为单位时间内产生的资源的数量。

输出格式

一个数字，表示资源数量达到T时的最少时间。

注意：与魔兽争霸3不同，魔兽争霸4中，生产苦工不需要时间。并且资源的采集并不连续，亦即如果一个苦工的效率为$2$，他会在时间为$1$的时候收获$2$点资源，而并不会在时间为$0.5$的时候收获$1$点资源。

输入输出样例

输入 #1

1 1 8
1 1

输出 #1

4

输入 #2

2 1 8
1 1
2 8

输出 #2

3

数据范围

对于$30 \%$的数据，$N \le 10, M, T \le 300$

对于$100 \%$的数据，$N \le100，M, T \le 1000, A, B \le 2^{31}$

数据保证有解。

解题报告

题意理解

1. 就是有若干类苦力,每一个苦力有一个,每秒生产力,和购买需要花费的资源.苦力可以无限购买

2. 初始的时候,你有一些资源,且问你达到目标资源数量的最少时间.

3. 购买苦力是不需要花费时间.

算法解析

这道题目是极为罕见的两次DP算法.

首先我们需要,固定花费$x$资源,可以购买最大的生产力为多少.
$$ f[x]表示花费x个资源,购买的最大生产力 $$

1. 每一个苦力看作一个物品
2. 每一个苦力,可以无限购买
3. 要求固定的资源,购买最大的生产力

其实这个就是完全背包问题.

然后我们考虑,对于有固定的资源数量,在一个固定的时间内,所拥有的最大生产力
$$ f2[t][x]表示t个时间内,拥有x个资源的最大生产力 $$
那么我们显然是要,购买生产力

那么,假设我们花费$k$个资源,那么得到最大多少生产力?
$$ f[k] $$
这就是我们上次完全背包的产物.

那么下一秒,我们会拥有多少资源呢.
$$ w=(j-k)+(f[k])+(f2[i][j]) \\\\下一秒资源=剩余资源+本次新来生产力制造的资源+原本就有的生产力制造的资源 $$
那么根据本次推导,下一秒最大生产力为多少呢?
$$ f2[i+1][w]=max(f2[i+1][w],f[k]+f2[i][j]); $$
既然如此,我们就成功的推导出来了,第二次的线性动态规划算法.

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=1100;
int a[N],b[N],f[N],f2[N][N],n,m,ed;
inline void init()
{
    scanf("%d%d%d",&n,&m,&ed);
    for(int i=1; i<=n; i++)
        scanf("%d%d",&a[i],&b[i]);
    if (m>=ed)
    {
        puts("0");
        return ;
    }
    memset(f,-1,sizeof(f));//消耗j点资源,可以得到的最大生产力
    f[0]=0;
    for(int i=1; i<=n; i++)
        for(int j=a[i]; j<=1000; j++)//完全背包转移
            if (f[j-a[i]]!=-1)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
    memset(f2,-1,sizeof(f2));//-1是为了处理是否拥有这么多资源
    f2[0][m]=0;//初始化,f2[i][j]表示i单位时间后剩下j资源能拥有的最大生产力。
    for(int i=0; i<=1000; i++)//i时刻
    {
        if (f2[i][ed]!=-1)//存在这种方案
        {
            printf("%d\n",i);
            return ;
        }
        for(int j=0; j<=ed; j++)//当前拥有j点资源
        {
            if(f2[i][j]==-1)//判断是否当前拥有这么多资源
                continue;
            for(int k=0; k<=j; k++)//花费k点能量购买生产力
            {
                if (f[k]==-1) //要保证k可以制造生产力
                    continue;
                int w=(j-k)+(f[k])+(f2[i][j]);//剩余资源+本次新来生产力制造的资源+原本就有的生产力制造的资源=下一秒资源 
                if (w>=ed)//发现找到了
                {
                    printf("%d\n",i+1);
                    return ;
                }
                f2[i+1][w]=max(f2[i+1][w],f[k]+f2[i][j]);//本次购买生产力+原本拥有的生产力 
            }
        }
    }
}
signed main()
{
    init();
    return 0;
}