洛谷 P1336 最佳课题选择题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了洛谷 P1336 最佳课题选择题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

P1336 最佳课题选择题解

题目链接

题目分析

状态：考虑 \(f_{i,j}\) 表示前 \(i\) 种论文里面，一共写了 \(j\) 篇，的最少花费时间。

转移策略：我们一次考虑每一种论文写多少篇。假设写 \(k\) 篇，\(k \in [0,j] \cap \mathbb{Z}\) ，有转移方程：

\[f_{i,j} = \min(f_{i-1,j-k} + \text{cost}(i,k)), k \in [0,j] \cap \mathbb{Z} \]

其中

\[\text{cost}(i,k) = a_i \times k ^ {b_i} \]

可以做记忆化优化，因为多次访问同一个 \(cost(i,k)\)。

初始化：我们考虑选0篇无论怎样花费为0，选0种论文但多于0篇一定是不可能的，花费为Inf，再加上转移中要取min的缘故，我们初始化为：

\[f_{i,j}= \begin{cases} 0 & ,j=0\\ + \inf &, j \neq 0\\ \end{cases} \]

和背包问题对比

这里和01背包及无限背包做个对比。

01背包的转移选择策略，是一个一个选（同时也是一种一种选，因为一种里面只有一个）。转移方程：

\[f_{i,j} = \max(f_{i-1,j}, f_{i-1,j-c_i} + v_i) \]

无限背包的转移选择策略，是在一种里面一个个选。转移方程：

\[f_{i,j} = \max(f_{i-1,j}, f_{i,j-c_i} + v_i) \]

可以看到两者细微的差别在，选物品的时候，01背包访问 \(i-1\)，无限背包访问 \(i\)，所以可以把其中一个维度压缩掉之后，01反着做，无限正着做。

本题目有两点不同：

第一，本题相当于“选择超过某价值的物品，使得容量需要量最小”，把状态的内外对换了一对。

第二，本题目中，如果选了前面一个，那么后面再选的时候，贡献会不一样，因为时间贡献是幂级的而非线性的。类比到无限背包中就是“选的越多，价值越少”，已经选了多少会影响到后面选的东西。选同一个东西的贡献，在不同情况下不一样。

于是，按照无限背包“一个一个”选的策略，就会涉及到之前的选择情况，我们尝试把第 \(i\) 种选择数目 \(k\) 加入到状态中，有

\[f_{i,j,k(k \leq j)}= \begin{cases} f_{i,j-1,k-1} - \text{cost}(i,k-1) + \text{cost}(i,k) & ,k \neq 0\\ \min(f_{i-1,j,l}), l \in [0,j] \cap \mathbb{Z} &, k = 0\\ \end{cases} \]

这样是正确的，但是我们发现大多数的状态被浪费了，因为 \(k \neq 0\) 的时候只有一种选择。

还有一种方式是把 \(f_{i,j}\) 中选择了多少个第i种论文，另存为 \(g_{i,j} = k\)，于是我们有转移方程(错误的)：

\[f_{i,j}=\min\left( \begin{array}{} f_{i,j-1} - \text{cost}(i,g_{i,j-1}) + \text{cost}(i,g_{i,j}), g_{i,j} = g_{i,j-1} + 1 ,\\ f_{i-1,j}, g(i,j) = 0 \end{array} \right) \]

这个转移方程看上去好像是对的，因为就是按照无限背包的思路改的，但实际上是错误的，提交后只能有10分。因为理论上这种转移方程只能处理线性的 \(\text{cost}(i,k)\)，即 \(b_{i} = 1\) 或 \(b_{i} = 0\)

我们和无限背包进行对比：假设有 \(f_{1,1} = 12\)，\(f_{1,2} = 24\)，\(f_{2,1} = 2\)，那么对于无限背包问题，有：

\[\begin{array}{} f_{2,2} = \max(f_{1,2},f_{2,1} + v_{2})\\ \because f_{2,1} = \max(f_{1,1},f_{2,0} + v_{2}) \neq f_{1,1}\\ \therefore f_{2,1} \geq f_{1,1}\\ \therefore f_{2,1} + v_{2} \geq f_{1,1} + v_{2} \end{array} \]

因此 \(f_{1,1} + v_{2}\) 不会影响 \(f_{2,1} + v_{2}\) 对\(f_{2,2}\) 可能的贡献，也就是不可能贡献（被max掉了）。

但是在这个问题中，我们令\(w_{i,k} = \text{cost}(i,k) - \text{cost}(i,k-1)\)，有:

\[\begin{array}{} f_{2,2} = \min(f_{1,2},f_{2,1} + w_{2,1})\\ \because f_{2,1} = \min(f_{1,1},f_{2,0} + w_{2,2}) \neq f_{1,1}\\ \therefore f_{2,1} \leq f_{1,1}\\ \therefore f_{2,1} + w_{2,2} \quad? \quad f_{1,1} + w_{2,1} \end{array} \]

可以发现我们无法判断 \(f_{1,1} + w_{2,1}\) 对于\(f_{2,2}\)是否有贡献，其根源在于对于同一个 \(i\)，\(w_{i,k}\) 是可能不同的，因此不等式失效，即在这种状态和转移方程下，不满足最优子结构。因此DP失效。

（这也说明，一个可DP的问题是存在“最优子结构”“无后效性”，只有特定的方式去“成立”这些性质才能DP，不是随便搞一搞就一定可以DP的）

也就是说，在无限背包问题中，我们把一个物品拿走，从规模更小的状态中转移，这个物品的贡献是确定的，决定“拿走”这一选择中的最优解，就只能是承接之前的最优解。

然而在这个问题中，如果我们把一个物品拿走，从规模更小的状态中转移时，这个物品的贡献是不确定的，也就是说除了最优解以外，次有解也有可能贡献出更好的结果，因此“最优子结构失效了”。

因此，我们在考虑状态和状态转移方程时，可以灵活更改状态、转移方式和策略、记录信息等等，同时也要按照普适状况考虑转移的合法性和具体转移方法。文章来源地址https://www.toymoban.com/news/detail-630796.html

标准AC代码：

#include <bits/stdc++.h>

#define N (int)(205)
#define M (int)(25)

using namespace std;

typedef long long LL;

int n,m;
LL f[N];
LL a[M],b[M];
LL p[M][N];

LL cost(int i, int k)
{
	if(p[i][k] == -1)
		return p[i][k] = a[i] * pow(k,b[i]);
	else
		return p[i][k];
}

int main()
{
	memset(p,-1,sizeof(p));
	memset(f,0x7f,sizeof(f));
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++) cin >> a[i] >> b[i];
	f[0] = 0;
	for(int i = 1;i <= m;i++)
	{
		for(int j = n;j >= 1;j--)
		{
			for(int k = 0;k <= j;k++)
			{
				f[j] = min(f[j],f[j-k] + cost(i,k));
			}
		}
	}
	cout << f[n];
	return 0;
}

另一种AC的代码：

#include <bits/stdc++.h>

#define N (int)(205)
#define M (int)(25)

using namespace std;

typedef long long LL;

int n,m;
LL f[M][N][N];
LL a[M],b[M];
LL p[M][N];

LL cost(int i, int k)
{
	if(p[i][k] == -1)
		return p[i][k] = a[i] * pow(k,b[i]);
	else
		return p[i][k];
}

int main()
{
	memset(p,-1,sizeof(p));
	memset(f,0x7f,sizeof(f));
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++) cin >> a[i] >> b[i];
	for(int i = 0;i <= m;i++) f[i][0][0] = 0;
	for(int i = 1;i <= m;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			for(int l = 0;l <= j;l++)
			{
				f[i][j][0] = min(f[i][j][0],f[i-1][j][l]);
			}
			for(int k = 1;k <= j;k++)
			{
				f[i][j][k] = f[i][j-1][k-1] - cost(i,k-1) + cost(i,k);
			}
		}
	}

	LL ans = 1e18;
	for(int k = 0;k <= n;k++)
		ans = min(ans,f[m][n][k]);
	cout << ans;
	return 0;
}

到了这里，关于洛谷 P1336 最佳课题选择题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

洛谷 P1336 最佳课题选择题解

P1336 最佳课题选择题解