zcmimi's blog

划分dp

题意

每组输入是两个整数nk(1\le n \le 50, 1 \le k \le n)

输出

对于输入的n,k;

第一行: 将n划分成若干正整数之和的方案数。

第二行: 将n划分成k个正整数之和的方案数。

第三行: 将n划分成最大数不超过k的方案数。

第四行: 将n划分成若干个奇正整数之和的方案数。

第五行: 将n划分成若干不同整数之和的方案数。

第六行: 打印一个空行

Sol.:

划分的多个正整数可以相同

f[i][j]表示将i划分成不大于j的整数的方案数

  1. i<j时,i不能划分为大于i的数,所以f[i][j]=f[i][i]
  2. i>j时,分为两种情况

    • 划分中后的数含有j

      方案数:f[i-j][j](i<j)

    • 划分中不含j

      相当于把i划分成不大于j-1的数 方案数:f[i][j-1]

    所以f[i][j]=f[i-j][j]+f[i-1][j-1](i>j)

  3. i=j时,两种情况:

    • 划分后的数只含有j,那么只有一种情况
    • 相当于把i划分成不大于j-1的数 方案数:f[i][j-1]

    所以f[i][j]=1+f[i][j-1]

f[n][n]:将n划分为若干正整数之和的划分数

f[n][k]:将n划分成最大数不超过k的划分数。

划分的正整数必须不同

f[i][j]表示将i划分成不大于j的不同整数的方案数

  1. i<j时,i不能划分为大于i的数,所以f[i][j]=f[i][i]
  2. i>j时,分为两种情况

    • 划分后的数中含有j

      其余的不能含有j

      方案数:f[i-j][j-1](i<j)

    • 划分中不含j

      相当于把i划分成不大于j-1的数

      方案数:f[i][j-1]

    所以f[i][j]=f[i-j][j-1]+f[i-1][j-1](i>j)

  3. i=j时,两种情况:

    • 划分后的数只含有j,那么只有一种情况
    • 相当于把i划分成不大于j-1的数 方案数:f[i][j-1]

    f[i][j]=1+f[i][j-1]

f[n][n]:将n划分为不同正整数之和的划分数

将n划分为k个正整数的划分数

f[i][j]为将i划分为j个正整数的方案数

  1. i<j,不可能出现,f[i][j]=0(i<j)
  2. i=j, 只有一种情况:划分成i1
  3. i>j,两种情况:

    • 划分后的数中含有1

      可以使用“截边法”将划分出的j个数分别减去1,把问题转化为将i-j划分成j-1个数,方案数:f[i-j][j-1]

    • 划分后的数中不含1

      使用“截边法”将划分出的j个数分别减去1,将为题转化为求i-jj个划分数,为f[i-j][j]

      所以f[i][j]=f[i-j][j-1]+f[i-j][j]

f[n][k]表示将n划分为k个正整数的方案数

将n划分为若干正奇数之和的划分数

f[i][j]为将i划分为j个奇数之和的划分数,

g[i][j]为将i划分为j个偶数之和的划分数

使用截边法,将g[i][j]j个划分都减去1,可以得到f[i-j][j],所以

g[i][j] = f[i-j][j]

对于f[i][j]

  1. 划分后的数中包含1

    可以将划分出的1除去,转化为“将i-1划分为j-1个奇数之和的划分数

    f[i-1][j-1]

  2. 划分后的数中不含1

    使用截边法将划分出的j个数每一个都减去1

    转化为“将i-j划分为j个偶数之和的划分数”,

    g[i-j][j]

所以f[i][j]=f[i-1][j-1]+g[i-j][j]

\sum_{i=0}^nf[n][i]表示将n划分为若干奇数的方案数

划分dp
comment评论
Search
search