1,题意:m个房子,n只小猪,(n>=m),房间保证住满,问共有多少种方案?
2,解答:动态规划
d[i][j]:j只小猪住i个房子的方案.
初始化:d[i][j]=0,d[1][j>=1]=1;
状态转移:
d[i][j]=1;(i==j)
d[i][j]=d[i-1][j-1]+d[i][j-1]*i;(i<j)
3,实例代码:
#include <iostream>
using namespace std;
const int maxL=250;
struct big_num
{
int a[maxL];
public:
void init()
{
memset(a,0,sizeof(a));
}
big_num operator=(int obj)
{
init();
int n=0;
while(obj)
{
a[n++]=obj%10000;//1位放四位数
obj/=10000;
}
return *this;
}
big_num operator*(int obj)
{
big_num other;
other.init();
int add=0;//进位
int n;//最高位的下标
for(n=maxL-1;n>=0&&!a[n];n--);
int i;
for(i=0;i<=n;i++)
{
other.a[i]=(a[i]*obj+add)%10000;
add=(a[i]*obj+add)/10000;
}
other.a[i]=add;
return other;
}
big_num operator+(big_num obj)
{
big_num other;
other.init();
int add=0;//进位
for(int i=0;i<maxL;i++)
{
other.a[i]=(a[i]+obj.a[i]+add)%10000;
add=(a[i]+obj.a[i]+add)/10000;
}
return other;
}
void output()
{
int n;//最高位的下标
for(n=maxL-1;n>=0&&!a[n];n--);
if(n<0)
{
cout<<"0"<<endl;
return;
}
for(int i=n;i>=0;i--)
{
if(i==n) cout<<a[i];
//可能全0,所以需要一位一位处理
else
{
int temp=a[i];
int k=1000;
while(k)
{
cout<<temp/k;
temp%=k;
k/=10;
}
}
}
cout<<endl;
}
};
const int maxN=100;
big_num d[maxN][maxN]; //状态数组
void initState()
{
for(int i=0;i<maxN;i++)
for(int j=0;j<maxN;j++)
d[i][j]=0;
for(int i=1,j=1;j<maxN;j++)
d[i][j]=1;
}
int cnt;
int main()
{
freopen("5.7.in","r",stdin);
cin>>cnt;
int n,m;//小猪数和房子数
while(cnt--)
{
cin>>n>>m;
initState();
for(int i=1;i<=m;i++)
for(int j=i;j<=n;j++)
{
if(i==j) d[i][j]=1;
else
d[i][j]=d[i-1][j-1]+d[i][j-1]*i;
}
d[m][n].output();
}
return 0;
}
分享到:
相关推荐
国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集
本系列丛书包括《ACM国际大学生程序设计竞赛:知识与入门》、《ACM国际大学生程序设计竞赛:算法与实现》、《ACM国际大学生程序设计竞赛:题目与解读》、《ACM国际大学生程序设计竞赛:比赛与思考》等4册,其中《ACM...
国际大学生程序设计竞赛例题解(六) 广东省大学生程序设计竞赛例题解析
第三本:国际大学生程序设计竞赛例题解 3 图论·动态规划算法·综合题专集 第四本:国际大学生程序设计竞赛例题解 4 广东省信息学奥林匹克竞赛试题 2003-2006年 第五本:国际大学生程序设计竞赛例题解 5 广东省...
此资源压缩包分为两卷,此卷为part1。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛例题解二,分享给大家!
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛例题解 广东省大学生程序设计竞赛试题,搞ACM,信息学竞赛的同学都用得着!
国际大学生程序设计竞赛例题解.一:数论、计算几何、搜索算法专集.
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
为了帮助高等院校的大学生们备战国际大学生程序设计竞赛,帮助他们提高程序设计水平和培养更强的分析问题和解决问题的能力,我们编写了这本辅导教材。本书所用的语言是Pascal(Delphi)。全书共分六章,第1章先介绍...
中国大学生数学建模竞赛题解_matlab
此资源压缩包分为两卷,此卷为part2。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
国际大学生程序设计竞赛(ACM)例题解析合集八本1-8,设计到各类算法的方方面面,包括动态规划、图论、搜索算法等。对于做算法开发的程序员很有参考意义。 附件为百度网盘永久链接地址。
国际大学生程序设计竞赛例题解 6 广东省大学生程序设计竞赛试题解 2008-2009年 郭嵩山 电子工业出版社
国际大学生程序设计竞赛例题解赛试题(一)