首页 > 代码库 > Buy the Ticket HDU 1133 递推+大数
Buy the Ticket HDU 1133 递推+大数
题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=1133
题目大意：
有m+n个人去买电影票，每张电影票50元， m个人是只有50元一张的， n个人是只有100元一张的， 电影院自己本身是没有零钱的。 那么要收到100元的钱必须找人家50， 那么再次之前就必须
收到一个50元的， 问你有多少种不同的排列方式。 （注意： 这里每个人都看成了不同的元素）
题目分析：
我们要是能找人家钱首先必须要有 m >= n
我们dp[m][n] 再加一个人 只能又 dp[m-1][n] 和 dp[m][n-1] 转化而来
假设m-1 > n 前面的所有状态都合法
那么 再加入一个带50元人时， 此人的合法的安插位置应该有 m 个， 我们先把这第m个50元的人放在最后， 是 1 种绝对是合法的，因为dp[m-1][n]是合法的放在最后是不影响结果的
我们放在最后这个人可以和前门的 （m-1）个人中的任意一个互换位置， 形成 (m-1) 种情况 加上之前的 1种 总共是 m 种， 同理我们可以推出 n的 情况
递推公式：
dp[m][n] = dp[m-1][n]*m + dp[m][n-1]*n
因为此题的数据范围是100 所以需要用到大数来写
#include <iostream>#include <queue>#include <cstdio>#include <cstring>#include <cstdlib>#include <stack>#include <algorithm>#include <vector>#include <string>#include <cmath>using namespace std;const long long maxn =120;const long long INF = 0xfffffff;int dp[maxn][maxn][maxn*5];void Slove(){ dp[1][0][0] = 1; for(int i=1; i<maxn; i++) { for(int j=0; j<=i; j++) { for(int k=0; k<5*maxn; k++) { dp[i][j][k] += dp[i-1][j][k]*i + dp[i][j-1][k]*j; dp[i][j][k+1] += dp[i][j][k]/10; dp[i][j][k] %= 10; } } }}void Putt(int m,int n){ int i; for(i=5*maxn-1; i >=0; i--) { if(dp[m][n][i] != 0) break; } for(; i >=1; i--) printf("%d", dp[m][n][i]); printf("%d\n",dp[m][n][0]);}int main(){ Slove(); int m, n, cas = 1; while(cin >> m >> n, m+n) { cout << "Test #" <<cas++ <<":" << endl; Putt(m,n); } return 0;}/*dp[m][n] = dp[m-1][n]*m + dp[m][n-1]*n*/
Buy the Ticket HDU 1133 递推+大数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。