798236606 发表于 2020-2-7 11:34:10

PTA A_1103 Integer Factorization

本帖最后由 798236606 于 2020-2-7 11:34 编辑

传送门：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, 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;

    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, p);
            
            if (i < ans.size() - 1)
                printf(" + ");
      }      
    }
    else
      puts("Impossible");
      
    return 0;   
}
页: [1]
查看完整版本: PTA A_1103 Integer Factorization