XDOJ1144

Problem 1144 - 組合數學三之棋魂 Time Limit: 1000MS      Memory Limit: 65536KB      Difficulty:    

Total Submit: 61     Accepted: 24     Special Judge: No  Description 嗯，首先是故事預告：國小六年級的進藤光為了賺些零用錢，跑到爺爺家裡尋寶，偶然翻出了一個舊棋盤。接觸棋盤的一瞬間，附身于棋盤中的平安時代棋士——藤原佐為的靈魂進入了小光的體内。佐為将圍棋視為生命，在他的熏陶下，小光也逐漸對圍棋産生了興趣…… 個人認為圍棋中最為枯燥乏味的莫過于整理棋子，比如現在光所要做的工作。先有n個黑色的棋子，m個一樣的盒子，問：光有多少種不同的方法，可以将棋子全部放到盒子中去？？

Input 每一行有一個m和n（1<m<=n<1000） Output 每一行輸出一個可能的個數（模10007取餘）

Sample Input 2 4

1 5 Sample Output 3

1   這題看到後我就想到了轉化成拆分數來處理。

他的模型原型就是n個相同小球放進m個相同盒子且不允許出現空盒的方法。。上篇文章中隻說是dp處理，沒說怎麼處理，那麼這篇文章就談談這種方法。都說了是拆分數了，那麼直接看看拆分數吧。

所謂拆分數就是把給定的一個整數拆成幾個正整數之和的方法數。(且其中最大加數m不大于n)

如給定整數為n=6;

則可以拆分為  ：6,  5+1，4+2， 4+1+1，  3+3， 3+2+1, 3+1+1+1，2+2+2， 2+2+1+1,  2+1+1+1+1, 1+1+1+1+1+1;

總共11種方法。

下面分析一下這個一般性的規律：

假設用dp[n][m]來表示把n拆分(且其中m為最大加數)的方法數；

那麼，首先第一種情況：

(1)：         當n或m等于1時隻有1種拆分方式，從上面的例子很明顯可以看出。

(2):           下面看n和m的關系來讨論.

當m>n時，實際上最大加數m不可能大于n，故這種情況下dp[n][m]=dp[n][n];

當m==n時，從上面的例子可以觀察出來，此時的情況數為不大于n的最大加數拆分一下再加上1就行，即dp[n][m]=dp[n][m-1]+1;

當m<n時，也是最普遍的情況。此時恰好就是把n拆分出來且保證了最大加數不大于n的情況。。

觀察上述例子，假設m=4的話。此時就是求dp[6][4]，這個就相當于最大加數小于4拆分一下的情況再加上6-4=2拆分一下的情況。

此時的方程就是:  dp[n][m]=dp[n][m-1]+dp[n-m][m]。

有了上述結論;很容易就能寫出本題的代碼。

不細心，然後各種CE ，WA。。。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

int m,n;
const int maxn=1000+5;
const int mod=10007;

long long dp[maxn][maxn];

int main()
{
    for(int i=1;i<=1001;i++)
    dp[i][1]=1;

    for(int i=1;i<=1001;i++)
    {
        for(int j=2;j<=1001;j++)
        {
            if(i==j)
                dp[i][j]=(dp[i][j-1]+1)%mod;
            else if(i>j)
                dp[i][j]=(dp[i][j-1]+dp[i-j][j])%mod;
            else if(i<j)
                dp[i][j]=dp[i][i];
        }
    }

    while(scanf("%d%d",&m,&n)!=EOF)
    {
        printf("%lld\n",dp[n][m]);
    }
    return 0;
}