1103 Integer Factorization (30分)/DFS+剪枝/打表

问题描述

分析

用DFS算法，每次只要当前数m满足pow(m,p)<=n即将其加入到temv中。这里为了把所有可能结果都存下来，用的是vector<vector< int > >。把递归式和递归边界写好代码就基本出来了。

初步成型代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<vector<int>> v;
bool cmp(vector<int> &a, vector<int> &b) {
	int suma = 0,sumb=0;
	for (int i : a) suma += i;
	for (int i : b) sumb += i;
	if (suma != sumb) return suma > sumb;
	else {
		return a > b;
	}	
}
void dfs(vector<int> &temv,int n,int k,int &p,int maxm) {
	if (k == 0) {
		if (n == 0) v.push_back(temv); //如果刚好n==0则将temv将入到v中
		return;
	}	
	for (int m = 1; pow(m, p) <= n&&m<=maxm; m++) {
		temv.push_back(m);
		//由于最后答案是非递增序列，所以每次m不能超过上一层递归的m（maxm）
		dfs(temv, n - pow(m, p), k - 1, p, m); 
		temv.pop_back(); //由于temv是引用类型，前面的push也会改变上一层的temv，因此需要pop
	}
}
int main() {
#ifdef ONLINE_JUDGE
#else
	freopen("1.txt", "r", stdin);
#endif
	int n, k, p; cin >> n >> k >> p;
	vector<int> temv,ans;
	int maxm;
	for (maxm = 1; pow(maxm, p) <= n; maxm++);
	dfs(temv, n, k, p,maxm);
	if (v.size() == 0) puts("Impossible");
	else {
		for (auto temp : v) {
			if (cmp(temp,ans)) ans = temp;
		}
		printf("%d = ", n);
		for (int i = 0; i < ans.size(); i++) {
			if (i != 0) cout << " + ";
			printf("%d^%d", ans[i], p);
		}
	}
	return 0;
}

存在的问题

有一个递归层数比较多的测试点无法通过，则需要对代码进行优化。
（1）无需保存所有满足的序列，可以在递归的过程中进行比较，只保存一个最优解；
（2）每次temv的push_back、pop_back都需要重新分配内存空间，比较耗时，由于答案的序列长度是确定的，可以将ans序列初始化为定长的，这样在递归的过程中就不需要push、pop
（3）pow的计算结果可以保存下来，以免重复计算，耗用多余的时间；

优化后的代码

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

int n, k, p;
int opt,num,temsum;
vector<int> temv, ans;
void dfs(int n,int temk,int &p,int maxm) {
	if (temk == 0) {
		if (n == 0) {
			num++;
			if (temsum > opt) { //大于最优和
				opt = temsum;
				ans = temv;
			}
			else if (temsum == opt && temv > ans) ans = temv;
		}
		return;
	}	
	for (int m = 1; m<=maxm; m++) {
		int POW = pow(m, p);
		if (POW > n) break;
		temv[k - temk] = m; temsum += m;
		dfs(n - POW, temk - 1, p, m);
		temsum -= m; //需要恢复temsum的值
	}
}
int main() {
#ifdef ONLINE_JUDGE
#else
	freopen("1.txt", "r", stdin);
#endif

	cin >> n >> k >> p;
	temv.resize(k);
	int maxm;
	for (maxm = 1; pow(maxm, p) <= n; maxm++);
	dfs(n, k, p, maxm);
	if (num == 0) puts("Impossible");
	else {
		printf("%d = ", n);
		for (int i = 0; i < ans.size(); i++) {
			if (i != 0) cout << " + ";
			printf("%d^%d", ans[i], p);
		}
	}
	return 0;
}

或许还可以继续优化

以下是优化后的代码运行时间，之前超时的测试点总算是通过了，但是用时900+ms，题目的时间限制是1200ms，所以还是挺悬的hhhh。

思考发现，还有两个点可以优化：
（1）由于上面的代码每次dfs函数m都是从小到大寻找，而题目要求两个序列的和相等时输出较大的那一个，因此上面的代码每次找到和相等的序列时都会进行一次覆盖ans的操作。可以将dfs函数调整为m每次从大到小寻找，这样在序列和相等时就不需要比较ans和当前序列哪个更大了（当前序列一定更小）。
（2）打表技巧
由于每次递归都需要进行pow()运算，且其中涉及很多重复运算，因此可以先把需要用到的结果打表记录下来，这样在需要用的时候直接取即可。

最终优化结果

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int n, k, p;
int opt,num,temsum;
vector<int> temv, ans, POW;
void dfs(int n,int temk,int maxm) {
	if (temk == 0) {
		if (n == 0) {
			num++;
			if (temsum > opt) {
				opt = temsum;
				ans = temv;
			}
		}
		return;
	}	
	for (int m = maxm; m>=1; m--) {
		if (POW[m] <= n) {
			temv[k - temk] = m; temsum += m;
			dfs(n - POW[m], temk - 1, m);
			temsum -= m; //需要恢复temsum的值
		}
	}
}
int main() {
#ifdef ONLINE_JUDGE
#else
	freopen("1.txt", "r", stdin);
#endif

	cin >> n >> k >> p;
	temv.resize(k);
	int maxm,tem;
	for (maxm = 0; (tem=pow(maxm,p)) <= n; maxm++) {
		POW.push_back(tem);  //打表
	}
	dfs(n, k, maxm-1);
	if (num == 0) puts("Impossible");
	else {
		printf("%d = ", n);
		for (int i = 0; i < ans.size(); i++) {
			if (i != 0) cout << " + ";
			printf("%d^%d", ans[i], p);
		}
	}
	return 0;
}