首页 > 代码库 > 盒子放球的DP
盒子放球的DP
URAL1114
题目大意:
有N个盒子,有红色和蓝色两种颜色的球。红球有A个,篮球有B个。现在随意的向盒子里放球,
每个盒子可以放一种颜色的球,也可以放两种颜色的球,也可以不放球。球不必全都放进盒子里。问:总共有多少种方法。
状态dp[i][j][k] 表示向i个盒子里放j个篮球和k个红球的方案数目
状态转移方程:dp[i][j][k]=对dp[i-1][jj][kk] (0<=jj<=j,0<=kk<=k) 求和
最终结果是:在n个盒子里放 不定数目的球的种类数和即 对dp[n][i][j](0<=i<=A,0<=j<=B)求和。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,a,b; typedef unsigned long long ull; //前 i 个 盒子里放 j 个a k 个b 的方案数 ull dp[25][25][25],fin; int main() { while(scanf("%d%d%d",&n,&a,&b)!=EOF) { memset(dp,0,sizeof(dp)); dp[0][0][0]=1; //d p[0][a][b]=1; fin=0; for(int i=1;i<=n;i++) for(int j=0;j<=a;j++) for(int k=0;k<=b;k++) { for(int jj=0;jj<=j;jj++) //j j=j for(int kk=0;kk<=k;kk++) dp[i][j][k]+=dp[i-1][jj][kk]; if(i==n) fin+=dp[i][j][k]; //fin+= } cout<<fin<<endl; } return 0; }
盒子放球的DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。