PTA A_1103 Integer Factorization

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

解：
1.深度优先遍历

#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

int n, k, p, maxsum = -1;
vector <int> temp, ans;

void DFS(int fac, int now, int sum)
{
    if (now == n && temp.size() == k)
    {
        if (sum > maxsum)
        {
            maxsum = sum;
            ans = temp;    
        }
            
        return;
    }    
    
    int num = now + (int)pow((double)fac, (double)p);

    if (num <= n && temp.size() < k)
    {    
        temp.push_back(fac);
        DFS(fac, num, sum + fac);
        temp.pop_back();
    }
        
    if (fac > 1)
        DFS(fac - 1, now, sum);
}

int main(void)
{
    scanf("%d %d %d", &n, &k, &p);
    
    DFS(20, 0, 0);//观察到n<=400且p >=2, 则最大的因数为20。

    if (ans.size())
    {
        printf("%d = ", n);
        for (int i = 0; i < ans.size(); i++)
        {
            printf("%d^%d", ans[i], p);
            
            if (i < ans.size() - 1)
                printf(" + ");
        }        
    }
    else
        puts("Impossible");
      
    return 0;    
}

2.深度优先遍历 + 因数优化

#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

int n, k, p, maxsum = -1;
vector <int> temp, ans, fac;

void DFS(int index, int now, int sum)
{
    if (now == n && temp.size() == k)
    {
        if (sum > maxsum)
        {
            maxsum = sum;
            ans = temp;    
        }
            
        return;
    }    
    
    int num = now + fac[index];

    if (num <= n && temp.size() < k)
    {    
        temp.push_back(index);
        DFS(index, num, sum + index);
        temp.pop_back();
    }
        
    if (index > 1)
        DFS(index - 1, now, sum);
}

int main(void)
{
    scanf("%d %d %d", &n, &k, &p);
    
    for(int i = 0; (int)pow((double)i, (double)p) <= n; i++)//直接算出所有可能的因数，存储在fac数组        
        fac.push_back((int)pow((double)i, (double)p));
    
    DFS(fac.size() - 1, 0, 0);

    if (ans.size())
    {
        printf("%d = ", n);
        for (int i = 0; i < ans.size(); i++)
        {
            printf("%d^%d", ans[i], p);
            
            if (i < ans.size() - 1)
                printf(" + ");
        }        
    }
    else
        puts("Impossible");
      
    return 0;    
}