• 【PAT甲级 - C++题解】1103 Integer Factorization


    ✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
    📚专栏地址:PAT题解集合
    📝原题地址:题目详情 - 1103 Integer Factorization (pintia.cn)
    🔑中文翻译:整数分解
    📣专栏定位:为想考甲级PAT的小伙伴整理常考算法题解,祝大家都能取得满分!
    ❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创作的最大动力💪

    1103 Integer Factorization

    The KP factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the KP factorization of N for any positive integers N, K and P.

    Input Specification:

    Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

    Output Specification:

    For each case, if the solution exists, output in the format:

    N = n[1]^P + ... n[K]^P
    
    • 1

    where n[i] (i = 1, …, K) is the i-th factor. All the factors must be printed in non-increasing order.

    Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122+42+22+22+12, or 112+62+22+22+22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence { a1,a2,⋯,aK } is said to be larger than { b1,b2,⋯,bK } if there exists 1≤LK such that ai=bi for i<L and aL>bL.

    If there is no solution, simple output Impossible.

    Sample Input 1:

    169 5 2
    
    • 1

    Sample Output 1:

    169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
    
    • 1

    Sample Input 2:

    169 167 3
    
    • 1

    Sample Output 2:

    Impossible
    
    • 1
    题意

    正整数 NK−P 分解,是将 N 写为 K 个正整数的 P 次幂的和。

    请你编写一个程序,给定 N,K,P 的情况下,找到 NK−P 分解。

    思路

    状态表示: f[i][j][k] 表示所有只考虑前 i 个物品,且总 p 次方和恰好是 j ,且数的个数恰好是 k 的所有选法的集合。

    这个集合意思是存的答案中用到的所有数的总和,比如 n = 169, k = 5, p = 2 的最佳拆分答案为 6^2 + 6^2 + 6^2 + 6^2 + 5^2 ,所以集合 f[5][169][5] = 6 + 6 + 6 + 6 + 5 = 29

    故我们需要先求出最佳的集合数,然后再反过来拆分集合得到最终的答案。

    代码
    #include
    using namespace std;
    
    const int N = 410;
    
    int n, k, p;
    int f[21][N][N];
    
    //计算a的b次方
    int power(int a, int b)
    {
        int res = 1;
        for (int i = 0; i < b; i++)    res *= a;
        return res;
    }
    
    int main()
    {
        cin >> n >> k >> p;
    
        //初始化
        memset(f, -0x3f, sizeof f);
        f[0][0][0] = 0;
    
        //开始dp
        int m;
        for (m = 1;; m++)   //从1开始向后枚举
        {
            int v = power(m, p);   //计算m的p次方
            if (v > n) break;  //如果当前枚举的数已经超过n,则dp结束
    
            //更新数据
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= k; j++)
                {
                    //不选当前数
                    f[m][i][j] = f[m - 1][i][j];
    
                    //选当前数
                    if (i >= v && j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);
                }
        }
    
        m--;
    
        //从得到的集合中开始拆分出答案
        if (f[m][n][k] < 0)    puts("Impossible");
        else
        {
            printf("%d = ", n);
            bool is_first = true;
            while (m)
            {
                int v = power(m, p);
                //判断答案集合中是否有m
                while (n >= v && k && f[m][n - v][k - 1] + m == f[m][n][k])
                {
                    if (is_first)    is_first = false;
                    else    printf(" + ");
    
                    printf("%d^%d", m, p);
                    n -= v, k--;
                }
                m--;
            }
        }
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
  • 相关阅读:
    【2023,学点儿新Java-08】HelloWorld.java案例小结 | EditPlus中的Java文件说明 | EditPlus 简介 | 详细分析:Java程序的编写、编译和运行过程
    Idea中好用的插件
    OPENCV简单阈值中的参数详解
    B/S架构:手术室麻醉信息管理系统源码
    mysql 快速上传数据
    使用Redis的可能引起的三个问题
    上海交大牵手淘宝成立媒体计算实验室:推动视频超分等关键技术发展
    8月SCI&SSCI期刊目录已更新,警惕这7本期刊
    PCB厚铜板的设计,这一点一定要注意
    【Linux进程间通信】二、pipe管道
  • 原文地址:https://blog.csdn.net/Newin2020/article/details/127656441