P3891 [GDOI2014] 采集资源 题解

题面。

看到大家都是两个动态规划的写法，来给大家讲一下只用一次动态规划的写法。

思路

设 \(f_{i,j}\) 表示工作效率为 \(i\)，获取 \(j\) 点资源所需的最短时间，不以苦工设状态是因为苦工会因为后面购买而改变，不太现实。\(tme\) 表示答案，即到达 \(t\) 点资源所需的最短时间。

从 \(0\) 到 \(t\) 枚举 \(i\) 和 \(j\)，接着枚举每一种苦工，用 \(k\) 表示第 \(k\) 种苦工，需要 \(a_k\) 的资源，效率为 \(b_k\)。像完全背包那样子推。具体的 f[i + b[k]][j - a[k]] = min(f[i + b[k]][j - a[k]] , f[i][j])，表示招募一个苦工，但注意这个苦工所需资源不能超过 \(j\)，很容易理解，由于目前状态只要求达到 \(j\) 点资源，当能够购买 \(b_k \ge j\) 的第 \(k\) 种苦工之前，就至少有了 \(j\) 点资源，就没必要再买了。

买了苦工后，自然效率变为 \(i+b_k\)，而资金只有 \(j-a_k\)，这时的最小时间要么是 \(f_{i+b_k,j-a_k}\)，要么就是 \(f_{i,j}\)。这应该是很容易便能想明白的。（因此，\(f\) 数组初始都设为极大值）

如果此时 \(i+b_k \ge t\)，说明此时如果买苦工的话效率就已经超过所需的 \(t\) 点资源了，那么 \(tme\) 就需要更新答案，与 \(f_{i,j}+1\) 求一个较小值。为什么是与 \(f_{i,j}+1\) 而不是 \(f_{i+b_k,j-a_k}\) 呢？

首先，\(f_{i+b_k,j-a_k}\) 可能越界。其次，效率超过 \(t\) 时其实就已经没有必要再买了，因为再等待一个单位时间后，现有的资源就变为 \(i+j\) 就会超过 \(t\)，感兴趣的同学可以自己去验证一下，所以 \(tme\) 与 \(f_{i,j}\) 取最小值。（这其实也是一个优化，即 \(i+b_k<t\) 才需要更新 \(f\) 数组）

在每次枚举完苦工种类后，也需要考虑如果此后一直不买苦工是否会需要更少的时间就能达到 \(t\) 点资源，即

if(i)
{
	tme = min(tme , (t - j + i - 1) / i + f[i][j]);
}

明显，当 \(i=0\) 时无论如何都不会到达 \(t\)，所以从 \(i=1\) 开始判断。同时也要注意当 \(m\) 一开始就大于 \(t\) 时直接输出 \(0\) 即可。

对于每一个 \(f_{i,i+j}\)，明显可以由 \(f_{i,j}\) 经过一个时间单位得到，这里也需要对 \(f_{i,i+j}\) 进行更新，即

if(i + j < t)
{
	f[i][i + j] = min(f[i][i + j] , f[i][j] + 1);
}

复杂度 \(O(nt^2)\)，能过。

请原谅我拙劣的表达，真的尽力了。

代码

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
inline ll QuickPow(ll a , ll b)
{
	if(b == 0)
	{
		return 1;
	}
	ll k = QuickPow(a , b>>1);
	if(b & 1)
	{
		return (k * k * a) % mod;
	}
	return (k * k) % mod;
}
ll n , m , t;
ll tme = 0x3f3f3f3f;
ll a[10000] , b[10000];
ll f[1001][1001];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> t;
	memset(f , 0x3f3f3f3f , sizeof(f));
	if(m >= t)
	{
		cout << 0;
		return 0;
	}
	fr(i , 1 , n)
	{
		cin >> a[i] >> b[i];
	}
	fr(i , 1 , m)
	{
		f[0][i] = 0;
	}
	fr(i , 0 , t)
	{
		fr(j , 0 , t)
		{
			fr(k , 1 , n)
			{
				if(a[k] < j)
				{
					f[i + b[k]][j - a[k]] = min(f[i + b[k]][j - a[k]] , f[i][j]);
					if(i + b[k] >= t)
					{
						tme = min(tme , f[i][j] + 1);
					}
				}
			}
			if(i)
			{
				tme = min(tme , (t - j + i - 1) / i + f[i][j]);
			}
			if(i + j < t)
			{
				f[i][i + j] = min(f[i][i + j] , f[i][j] + 1);
			}
		}
	}
	cout << tme;
	return 0;
}