PAT A 1103 动态规划解法_综合

题记

写这篇博客主要也是看到网上大部分解法都是采用DFS，说实话写这题时我也考虑过DFS，但还是担心会超时，因为不仅是一个值加入不加入这两种选择，它还可能被多次加入，其复杂度比单纯的指数还要高。但后来写完看看网上人家的解法，发现DFS还是能过的，最复杂的点时间大概在300ms左右，看起来裕度也还不错。不过采取动态规划解法，最长时间在十几ms，可见其时间复杂度上还是具有明显的优势。
在这里插入图片描述

基本思路

对几个记号的意义进行声明:

$V$ :题目所给的待分解的值，也就是我们所得到序列的对应幂次值之和
$N$ :需要选择，加入到最终序列的的数字个数
$W[i]$ :底数为i时对应题目所给指数的幂值

首先，有2个基本的简化措施：

事先打表记录好每个值对应幂次的值，避免反复计算
根据题目所给的幂次，确定出一个可能选择的最大值UpperBound，也就是 $\sqrt V$ ，这是因为幂次 $P$ 至少为2，大于这个上界必然会使得和式溢出

前面我们已经打好了表，知道每选择一个元素该对应的和会被填充多少，那么把原始问题稍加变形，就可以发现非常类似于无界背包问题了：
有K种物品，每种有各自的标签(底数)和不同的价值（对应的幂值），从中选择 $N$ 件物品使得其总价值恰好为 $V$ ，并且让这 $N$ 件物品的标签(底数)之和最大。
从上面这个简单的变形，已经基本能看出动态规划的原型。
除了要求和最大，当和最大出现多种选择时我们还需要输出字典序最大的那个(序列按数字降序排列)，这一点在DFS解法里比较好解决，在动态规划时就需要额外做一点工作，不过稍后可以看到，这实际上会是非常好解决的一点小问题，并不需要专门的排序函数来帮忙。

状态转移方程推导

接下来考虑动态规划里最重要的状态转移方程：

先回到问题本身，在这里，我们现在需要找 $N$ 个数，幂值之和为 $V$ ,面对一个底数 $i$ ，当考虑要不要把它选择进来时，对应的不再是简单的判断最大值，实际上，把它加入进来，那么接下来需要考虑的就是如何找 $N-1$ 个数，使得其幂值之和为 $V-W[i]$ 。可能我们能发现一个合理解，不过也可能这是并不能做到的。假设前面并不能找到这样的 $N-1$ 个数满足要求，那么这个数不能选择；假如可以找到 $N-1$ 个数满足其和为 $V-W[i]$ ，那么我们自然希望前面已经完好记录了找 $N-1$ 个数幂之和为 $V-W[i]$ 的最优结果，这样我们不用重复去考虑 $N-1$ 个数的退化情况，这也是动态规划比DFS节省时间的主要原因。

到这里，基本就可以确定动态规划的基本数据结构
我们使用 $dp[n][v]$ 表示用选择n个底数使得幂值总和为 $v$ 的最优解，根据题目的要求，它应该存储两个信息：

最优序列之和 sum
最优序列本身 seq

所以可以用一个结构体二维数组来表示，结构体包含一个int值和一个vector分别表示1、2两部分信息。
为了表示找不到符合要求的解，可以设置最有序列之和为0表示序列并不存在。
在求解 $dp[n_0][v_0]$ ，时，对所有可选的底数进行一趟遍历，也就是从1到UpperBound，选择 $i+dp[n_0-1][v_0-w[i]]$ 的最大值作为 $dp[n_0][v_0]$ 。
这里需要注意的一点时，当发现值出现相等时，需要判断字典序，对这种情况还需要加上一个 $for$ 循环，但是也很简单就可以实现。

到这里，我们就得到的所需的状态转移方程，可以写为:
$dp[n][v].sum=max(i+dp[n-1][v-w[i]].sum) \quad i=1\to UpperBound\\ dp[n][v].seq=dp[n-1][v-w[select]].seq+select$
上面的select表示最终选择的底数，当所有的底数无法找到有效解时，则不进行修改，所以在结构体初始化时最好给sum赋初值0，因为可能会被后面的查询。

至此，只剩下最后一个方面没有谈到，就是序列排序的问题。这里我们并不需要专门再调用排序函数，只需每次更新dp值，也就是从之前的序列扩充一个元素时，简单进行一步插入排序的过程即可，注意，只需要一步插入排序。因为假设前面的序列已经是有序的，那么新加入一个值后，让它归位也就使得整个序列有序了。初始只有一个值天然有序，所以按照这种策略，序列有序性可以继续满足。所以排序也不会占用什么时间和码量

边界条件

由于我们构建结构体时初始化 $dp[i][j].sum=0$ ，所以对于0件物品的边界 $dp[0][j]$ 就无需再设置了，对于1件物品的情况即求 $dp[1][j]$ ，那么 $j$ 从 $1$ 到 $V$ 遍历一下，若 $j=a^P$ ，那么 $dp[1][j].sum=a$ ，把该底数加入序列即可。这里为了优化一下，也可以在前面求各个底数的幂时顺带记录一下，因为所给的值最大为400，所以开个大小401的数组来记录各个幂值出现的情况，同时为了方便根据幂值直接得到底数，可以设置该数组对应下标存储的值是其底数。

源代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>using namespace std;
struct opti_info {  //最优解信息int sum = 0;vector<int> seq;
};
const int maxn = 401;
int value_list[500]; //记录所有可实现的幂值
opti_info dp[maxn][maxn];int main() {int val, seq_len, order;cin >> val >> seq_len >> order;int max_val = (int)pow((double)val, 1.0 / order);int *pow_list = new int[max_val + 1];pow_list[0] = 0;for (int i = 1; i <= max_val; i++) {pow_list[i] = pow((double)i, order);value_list[pow_list[i]] = i; //存其底数，方便加入序列}//dp[0][i]已经天然初始化为0for (int i = 0; i <=val; i++)  //这里求解dp[1][i]if (value_list[i]) {dp[1][i].sum = value_list[i];dp[1][i].seq.push_back(value_list[i]);}for (int i = 2; i <= seq_len; i++) {for (int v = 1; v <= val; v++) {vector<int> best_seq;int cur_max_sum = 0;int insert_val;for (int j = 1; j <= max_val; j++) {  if (pow_list[j] >= v) break;int temp_v = v - pow_list[j];if(dp[i-1][temp_v].sum>0){//可以实现if (cur_max_sum < dp[i - 1][temp_v].sum + j) {best_seq.clear();best_seq = dp[i - 1][temp_v].seq;best_seq.push_back(j);cur_max_sum = dp[i - 1][temp_v].sum + j;insert_val = j;}else if (cur_max_sum == dp[i - 1][temp_v].sum + j) {//需要比较序列大小bool raw_seq_lager = true;int len = dp[i - 1][temp_v].seq.size();for(int k=0;k<len;k++)if (best_seq[k] < dp[i - 1][temp_v].seq[k]) {raw_seq_lager = false;break;}if (!raw_seq_lager) {best_seq.clear();best_seq = dp[i - 1][temp_v].seq;best_seq.push_back(j);insert_val = j;}}}}if (cur_max_sum > 0) { //说明是一个可实现的组合dp[i][v].sum = cur_max_sum;int begin = best_seq.size() - 2; //最后一个为新插入的元素，可能导致变为无序//采用插入排序一轮排序就可以保证继续有序while (begin > -1 && best_seq[begin] < insert_val) {best_seq[begin + 1] = best_seq[begin];begin--;}best_seq[begin + 1] = insert_val;dp[i][v].seq = best_seq;}}}if (dp[seq_len][val].sum != 0) {vector<int> *pv = &dp[seq_len][val].seq;printf("%d = ", val);for (int i = 0; i <pv->size(); i++) {if (i) printf(" + ");printf("%d^%d", (*pv)[i], order);}}else printf("Impossible");return 0;
}