[wikioi]数的划分

划分型DP。最终的思路是，F[i][j]表示i分成j份，如果分出来的有1，那么去掉1，就是F[i-1][j-1]；如果没有1，那就都减1，就是F[i-j][j]（注意此时i>=2j）。那么F[i][j]=F[i-1][j-1]+F[i-j][j]
详细些的话，以sample为例：
7=5+1+1；
7=2+4+1；
7=3+3+1；
7=2+2+3；
我们可以把所有数的拆分分成2种情况，有1和没有1的2种
那么有1的部分全部减去1，变成
6=5+1；
6=2+4；
6=3+3；
这就是6的所有划分成2部分的划分了。
没有1的，我们把没有1的所有因子全部减去1
得到4=1+1+2；
这就是4的所有划分成3部分的划分了

这个推导其实一时难以想到，这篇文章里有个转化和推导，图有点意思，虽然最终还是上面的简洁直接：http://blog.****.net/re_cover/article/details/9383177
关于怎么想到F[i-j][j]这样的东西的，某人说，N个球放到K个盒子，因为盒子不为空，那么我先把每个盒子放一个球。这也是某种思路的来源吧。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <memory.h>

#define MAX(a, b) a>b?a:b

#define LEN_N 205

#define LEN_K 10

using namespace std;

int F[LEN_N][LEN_K];

int N;

int K;

void init()

{

    scanf("%d%d", &N, &K);

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

        for (int j = 1; j <= K; j++)

            F[i][j] = -1;

}   

int dp(int i, int j)

{

    // F[i][j] = F[i-1][j-1] + F[i-j][j];

    if (i < j || i == 0 || j == 0) return 0;

    if (i == j) return 1;

    if (F[i][j] != -1) return F[i][j];

    F[i][j] = dp(i-1, j-1) + dp(i-j, j);

    return F[i][j];

}

int main()

{

    init();

    int ans = dp(N, K);

    printf("%d\n", ans);

    return 0;

}

秒客网

[wikioi]数的划分

相关文章