洛谷 P1336 最佳课题选择 题解
P1336 最佳课题选择 题解
状态：考虑\(f_{i,j}\)表示前\(i\)种论文里面，一共写了\(j\)篇，的最少花费时间。
转移策略：我们一次考虑每一种论文写多少篇。假设写\(k\)篇，\(k \in [0,j] \cap \mathbb{Z}\) ，有转移方程：
其中
可以做记忆化优化，因为多次访问同一个\(cost(i,k)\)。
初始化：我们考虑选0篇无论怎样花费为0，选0种论文但多于0篇一定是不可能的，花费为Inf，再加上转移中要取min的缘故，我们初始化为：
相关变量范围见代码。
最后，我们就可以开滚动数组，或者倒序\(j\)优化掉一维。
代码在文末。
这里和01背包及无限背包做个对比。
01背包的转移选择策略，是一个一个选（同时也是一种一种选，因为一种里面只有一个）。转移方程：
无限背包的转移选择策略，是在一种里面一个个选。转移方程：
可以看到两者细微的差别在，选物品的时候，01背包访问\(i-1\)，无限背包访问\(i\)，所以可以把其中一个维度压缩掉之后，01反着做，无限正着做。
本题目有两点不同：
第一，本题相当于“选择超过某价值的物品，使得容量需要量最小”，把状态的内外对换了一对。
第二，本题目中，如果选了前面一个，那么后面再选的时候，贡献会不一样，因为时间贡献是幂级的而非线性的。类比到无限背包中就是“选的越多，价值越少”，已经选了多少会影响到后面选的东西。选同一个东西的贡献，在不同情况下不一样。
于是，按照无限背包“一个一个”选的策略，就会涉及到之前的选择情况，我们尝试把第\(i\)种选择数目\(k\)加入到状态中，有
这样是正确的，但是我们发现大多数的状态被浪费了，因为\(k \neq 0\) 的时候只有一种选择。
还有一种方式是把\(f_{i,j}\)中选择了多少个第i种论文，另存为\(g_{i,j} = k\)，于是我们有转移方程(错误的)：
这个转移方程看上去好像是对的，因为就是按照无限背包的思路改的，但实际上是错误的，提交后只能有10分。因为理论上这种转移方程只能处理线性的\(cost(i,k)\)，即\(b_{i} = 1\)或\(b_{i} = 0\)
我们和无限背包进行对比：假设有\(f_{1,1} = 12\)，\(f_{1,2} = 24\)，\(f_{2,1} = 2\)，那么对于无限背包问题，有：
因此\(f_{1,1} + v_{2}\)不会影响\(f_{2,1} + v_{2}\)对\(f_{2,2}\)可能的贡献，也就是不可能贡献（被max掉了）。
但是在这个问题中，我们令\(w_{i,k} = cost(i,k) - cost(i,k-1)\)，有:
可以发现我们无法判断\(f_{1,1} + w_{2,1}\)对于\(f_{2,2}\)是否有贡献，其根源在于对于同一个\(i\)，\(w_{i,k}\)是可能不同的，因此不等式失效，即在这种状态和转移方程下，不满足最优子结构。因此DP失效。
（这也说明，一个可DP的问题是存在“最优子结构”“无后效性”，只有特定的方式去“成立”这些性质才能DP，不是随便搞一搞就一定可以DP的）
也就是说，在无限背包问题中，我们把一个物品拿走，从规模更小的状态中转移，这个物品的贡献是确定的，决定“拿走”这一选择中的最优解，就只能是承接之前的最优解。
然而在这个问题中，如果我们把一个物品拿走，从规模更小的状态中转移时，这个物品的贡献是不确定的，也就是说除了最优解以外，次有解也有可能贡献出更好的结果，因此“最优子结构失效了”。
因此，我们在考虑状态和状态转移方程时，可以灵活更改状态、转移方式和策略、记录信息等等，同时也要按照普适状况考虑转移的合法性和具体转移方法。
标准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;
}