1103. Integer Factorization (30)

1.题面

https://www.patest.cn/contests/pat-a-PRactise/1103

2.题意

将一个数字分解成若干正整数幂之和，比如

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2如果存在多种分解，要求输出正整数之和最小的，如果还有多解要求输出字典序最小的
3.思路
貌似暴力搜索加剪枝也可以得到答案，但是搜索保存答案似乎更快，十几毫秒就过了
4.代码
/*****************************************************************    > File Name: cpp_acm.cpp    > Author: Uncle_Sugar    > Mail: uncle_sugar@QQ.com    > Created Time: Thu 16 Feb 2017 02:21:19 CST*****************************************************************/# include <cstring># include <iostream># include <iomanip># include <vector>using namespace std;const int size  = 10 + 1000 ; int n, k, p;vector<int>  vct;int vis[size][size];int fa_vis[size][size];int sum[size][size];int iniv[size];int ipow(int n, int k){    int ret = 1;    for (; k; k>>=1, n *= n){        if (k&1) ret *= n;    }    return ret;}int getAns(int _n, int _k){    if (vis[_n][_k] != -1) return vis[_n][_k];    int ret = 0;    for (int k = vct.size()-1; k >= 0; k--){        int i = vct[k];        if (_n - i >= 0 && getAns(_n - i, _k - 1)){            if (ret == 0){                fa_vis[_n][_k] = _n-i;                sum[_n][_k] = sum[_n-i][_k-1] + iniv[i];                ret = 1;            }else if (sum[_n][_k] < sum[_n-i][_k-1] + iniv[i]){                fa_vis[_n][_k] = _n-i;                sum[_n][_k] = sum[_n-i][_k-1] + iniv[i];            }        }    }    return vis[_n][_k] = ret;}int main(){    std::ios::sync_with_stdio(false);cin.tie(0);    memset(vis, -1, sizeof(vis));    fa_vis[0][0] = -1;    cin >> n >> k >> p;    for (int i = 1; i <= n; i++){        int t = ipow(i, p);        iniv[t] = i;        if (t > n) break;        vct.push_back(t);    }    for (int i = 0; i <= n; i++) vis[i][0] = 0;    vis[0][0] = 1;    if (getAns(n, k)){        cout << n;        char flag = 1;        while (fa_vis[n][k] != -1){            int t = fa_vis[n][k];            if (flag) cout << " =", flag = 0;            else cout << " +";            cout << " " << iniv[n-t] << "^" << p;            n = fa_vis[n][k]; --k;        }        cout << endl;    }else {        cout << "Impossible" << endl;    }    return 0;}