nbuoj 2080 洛谷p1025 数的划分

链接：http://www.nbuoj.com/v8.83/Problems/Problem.php?pid=2820

链接：https://www.luogu.org/problem/P1025

题意：将整数nn分成kk份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

思路一：可开for暴力，在搜索的过程中进行剪枝，并且可以计算得，最小的数不会大于200/6，即n/k，可以在第一层循环里修改：for(int i=1;i<=n/k;i++)

//保证i<=j<=k<=o<=p<=q的同时,如果i+j+k+o+p+q==n,则cnt++

for(int i=;i<=;i++)

{

    for(int j=i;i+j<=;j++)

    {

        for(int k=j;i+j+k<=;k++)

        {

            for(int o=k;i+j+k+o<=;o++)

            {

                for(int p=o;i+j+k+o+p<=;p++)

                {

                    int q=-i+j+k+o+p;

                    if(q>=p)cnt++;

                }

            }

        }

    }

}

思路二：dp，dp[i][j]表示i分成j堆有几种分法

转移方程：当i>j时，dp[i][j]=dp[i-j][j]+dp[i-1][j-1]，否则dp[i][j]=0

①k堆里至少有一堆是1，dp[i][j]=dp[i-1][j-1]

②k堆里每堆都大于1，dp[i][j]=dp[i-j][j]

终止条件：i=1或j=1或j=i时，dp[i][j]=1

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int dp[][]={},n,k;

    cin>>n>>k;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=k&&j<=i;j++) //j>i时肯定不能保证每堆都有数

        {

            if(i==||j==||j==i){dp[i][j]=;continue;}  //这三个可以由dp[0][0]=1代替...why？

            dp[i][j]=dp[i-j][j]+dp[i-][j-];

        }

    }

    cout<<dp[n][k]<<endl;

    return ;

}

巴特西

nbuoj 2080 洛谷p1025 数的划分

最新文章

热门文章