M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

【DP】TOJ 2820 How many different ways

给定从1 到 N的 N 个数,问有多少种不同方案划分这些数。比如N = 3,则有5种方案:
{{1},{2},{3}}
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
{{1,2,3}}
最后的结果只保留后四位,即mod10000;
上网查了下,集合的划分的个数叫做bell数,bell数可以递归求解:
bell[0] = 1;
bell [n + 1] = sigma(C(n,k))*(bell[k]); (0<=k<=n)

 
然而这个题却不可以这样做,因为N得范围是2000,这样做必定超时,于是想到了DP,如果用dp[i][j]表示i个数
划分成j个集合,那么便有dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];( i > j )直观理解就是,将i个数划分成j个集合的个数,即为i-1个数划分到j个集合的数,再将多的那个依次放到j个集合中,所以乘以j,或者是i-1个数放在j-1个集合中,第j个集合为空,则正好将多的这个数放到这个集合中,于是便有上边的状态转移方程。
Code:

 

#include <cstdio>
#include 
<iostream>
#include 
<cmath>
using namespace std;

int map[2002][2002];
void DP(){
    memset(map,
0,sizeof(map));
    
int i,j,k;
    
for(i = 0;i <= 2000; i++){
        map[i][i] 
= 1;
        map[i][
1= 1;
    }

    
for(i = 0;i <= 2000 ;i++)
        
for(j = 0; j < i; j++)
            map[i][j] 
= (j * map[i-1][j] + map[i-1][j-1])%10000;
}

int main()
{
    
int i,j,k,n;
    DP();
    
while(scanf("%d",&n),n){
        
int ans = 0;
        
for(i = 0;i <= n; i++)
            ans 
= (ans + map[n][i])%10000;
        
string str = "0000";
        str[
3= ans%10+'0'; ans/=10;
        str[
2= ans%10+'0'; ans/=10;
        str[
1= ans%10+'0'; ans/=10;
        str[
0= ans%10+'0'; ans/=10;
        cout
<<str<<endl;
    }

}

posted on 2010-06-12 15:05 M.J 阅读(228) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理