POJ1664 放苹果【dp：整数无序拆分】

悠悠 2022-11-18 01:50 40阅读 0赞

[poj1664][]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

dp[i][j]表示i个苹果考虑放进j个盘子里面
    考虑的意思就是不一定都会用到这j个盘子
    
    if(i>=j){ 
        dp[i][j] = dp[i-j][j] + dp[i][j-1];    
    }else{ 
        dp[i][j] = dp[i][i];
    }

#include<iostream>
    #include <string.h>
    using namespace std;
    
    typedef long long ll;
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    int dp[11][11];
    
    void cal(int m,int n){ 
        memset(dp,sizeof(dp),0);
        dp[0][0] = 0;
        
        for(int i=0;i<=m;i++){ 
            dp[i][1]= 1;
        }
        
        for(int j=0;j<=n;j++){ 
            dp[0][j]= 1;
        }
        
        for(int i=1;i<=m;i++){ 
            for(int j=2;j<=n;j++){ 
                if(i>=j){ 
                    dp[i][j] = dp[i-j][j] + dp[i][j-1];    
                }else{ 
                    dp[i][j] = dp[i][i];
                }
                
            }
        }
        
        cout<<dp[m][n]<<endl;
    }
    int main(){ 
        
        int m=0;
        int n=0;
        int t=0;
        cin>>t;
        for(int i=0;i<t;i++){ 
            cin>>m;
            cin>>n;
            cal(m,n);
        }
        
        return 0;
    }

关于整数的无序拆分除了递归的办法，还有母函数的方法  
[链接][Link 1]

[poj1664]: http://poj.org/problem?id=1664
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221022/062ce3c8b06f4a60bcbdae1a6273f252.png
[Link 1]: http://blog.chinaunix.net/uid-26548237-id-3503956.html

发表评论取消回复

表情：

评论列表（有 0 条评论，40人围观）

还没有评论，来说两句吧...

相关阅读

相关 343. 整数拆分

343. 整数拆分给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1

川长思鸟来/ 2024年03月26日 18:11/ 0 赞/ 80 阅读

相关【DP】CSL分苹果

典中典的DP啊过了我真牛逼 [1020-CSL分苹果\_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)][1020-CSL_2021_1

红太狼/ 2024年03月24日 10:23/ 0 赞/ 42 阅读

相关 343. 整数拆分

343. 整数拆分题干描述解题思路动态规划 1. 确定dp数组（dp table）以及下标的含义

小咪咪/ 2023年10月16日 16:05/ 0 赞/ 34 阅读

相关 343. 整数拆分

[343. 整数拆分][343.] 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入

た入场券/ 2023年03月03日 08:45/ 0 赞/ 7 阅读

相关 PTA--整数拆分

将一个正整数拆分成若干个正整数的和。输入格式: 一个正整数n 输出格式: 若干行，每行一个等式（每个数或者等号间都有一个空格，第一个数前没有空格，最后一个数后面没

刺骨的言语ヽ痛彻心扉/ 2022年12月27日 12:36/ 0 赞/ 158 阅读

相关 POJ1664 放苹果【dp：整数无序拆分】

[poj1664][] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9i

悠悠/ 2022年11月18日 01:50/ 0 赞/ 41 阅读

相关 343. 整数拆分

> 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。 > > 示例 1: > > 输入: 2 > 输出: 1

青旅半醒/ 2022年10月07日 00:50/ 0 赞/ 132 阅读

相关 Leetcode 343. 整数拆分(DP)

题目重述给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入: 2 输出:

秒速五厘米/ 2022年08月28日 02:50/ 0 赞/ 192 阅读

相关 pku 1664 分苹果(整数划分)

\include <iostream> using namespace std; int f(int m, int n) \{ if(m < 0) return 0; if(m

偏执的太偏执、/ 2022年08月13日 00:50/ 0 赞/ 107 阅读

相关 190512 | 整数拆分

题目描述一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1

淩亂°似流年/ 2022年01月31日 23:43/ 0 赞/ 233 阅读