Algorithm 版 (精华区)

发信人: Darcy (麦克思韦妖), 信区: Algorithm
标  题: ACM-2.1.1--动态规划法
发信站: 哈工大紫丁香 (2001年08月17日18:10:42 星期五), 站内信件

我也贴一片
方法是动态规划
arr[i,j] 表示将数i拆成大于等于j的个数。
程序如下：
vc 6,pII300,9s(显示)/3s(not display result)
const maxn=400;
__int64 arr[maxn][maxn+1];
__int64 f(int i,int j){
    if (arr[i][j]>=0) return arr[i][j];
    if (i==0) {
        arr[i][j]=1;
        return 1;
    }
    if (i<j){
        arr[i][j]=0;
        return 0;
    }
    arr[i][j]=0;
    for (int k=i-j;k>=0;k--)
        arr[i][j]+=f(k,i-k);
    return arr[i][j];
}
    
int main(int argc, char* argv[])
{
    for (int i=0;i<=maxn;i++)
        for (int j=0;j<=maxn;j++)
            arr[i][j]=-1;
    for (i=2;i<=maxn;i++)
//      printf("%d\t%I64d\n",i,f(i,1));
    f(i,1);
    return 0;
}


【 在 sino (茶水先生) 的大作中提到: 】
: 题目：整数拆分
:      将一个正整数n,拆分成一组小于n的正整数的和（不考虑排列的次序）。
: 求共有多少组可能的拆分。
: |============================================================|
: 这是我最近看的一个题。
: 此题可转化为利用母函数求不定方程解的个数的问题。
: 拆分中不选取1可表示为1 -- 此处指x的0次幂、系数为1。
: 拆分中选1个1可表示为X
: 拆分中选2个1可表示为X*X
:     .
:     .


--

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: biometrics.hit.edu.c]
※ 修改:·Darcy 於 08月17日18:19:09 修改本文·[FROM: biometrics.hit.edu.c]