1114. Boxes
2024-09-05 15:02:48
1114. Boxes
Time limit: 0.6 second
Memory limit: 64 MB
Memory limit: 64 MB
N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B
≤ 15). The red balls (and the blue ones) are exactly the same. You can
place the balls in the boxes. It is allowed to put in a box, balls of
the two kinds, or only from one kind. You can also leave some of the
boxes empty. It's not necessary to place all the balls in the boxes.
Write a program, which finds the number of different ways to place the
balls in the boxes in the described way.
≤ 15). The red balls (and the blue ones) are exactly the same. You can
place the balls in the boxes. It is allowed to put in a box, balls of
the two kinds, or only from one kind. You can also leave some of the
boxes empty. It's not necessary to place all the balls in the boxes.
Write a program, which finds the number of different ways to place the
balls in the boxes in the described way.
Input
Input contains one line with three integers N, A and B separated by space.
Output
The result of your program must be an integer written on the only line of output.
Sample
input | output |
---|---|
2 1 1 |
9 |
Problem Source: First competition for selecting the Bulgarian IOI team.
Tags: none (hide tags for unsolved problems)
Difficulty: 191 Printable version Submit solution Discussion (30)
My submissions All submissions (8069) All accepted submissions (2464) Solutions rating (2022)
My submissions All submissions (8069) All accepted submissions (2464) Solutions rating (2022)
思路:dp;
dp[n][i][j]表示放前n个盒子时,前n个盒子中的红球为i个,蓝球为j个的方案数,状态转移方程dp[n][i][j]=sum(dp[n-1][x][y])(x<=i&&y<=j);
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 typedef unsigned long long LL;
8 LL dp[40][40][40];
9 int main(void)
10 {
11 int i,j,k;
12 int n,m;
13 while(scanf("%d %d %d",&k,&n,&m)!=EOF)
14 {
15 memset(dp,0,sizeof(dp));
16 int x,y,z;
17 dp[0][0][0]=1;
18 int xx;
19 int yy;
20 LL sum=0;
21 for(i=1; i<=k; i++)
22 {
23 for(x=0; x<=n; x++)
24 {
25 for(y=0; y<=m; y++)
26 {
27 for(xx=0; xx<=x; xx++)
28 {
29 for(yy=0; yy<=y; yy++)
30 {
31 dp[i][x][y]+=dp[i-1][xx][yy];
32 }
33 }
34 if(i==k)
35 sum+=dp[i][x][y];
36 }
37 }
38 }
39 printf("%llu\n",sum);
40 }
41 return 0;
42 }
最新文章
- 介绍DSA数字签名,非对称加密的另一种实现
- dojo Provider(script、xhr、iframe)源码解析
- InstallUtil在windows服务中的使用(转)+ 服务安装的注意事项
- mssql手工注入及绕过术
- 修改RectTransform的值
- java工程包的命名(-dev.jar,-javadoc.jar,jar)
- [CSS]当选择器没有指定元素时
- 【Java】Java Platform
- 文件I/O实现cp复制功能
- 走进BFC
- ORACLE - 系统参数调整
- C:数据结构与算法之顺序表
- vue中引入vux
- SpringMVC 使用 MultipartFile 实现文件上传
- 绝对音乐No.1
- hdu 3727 Jewel (可持久化线段树+bit)
- BZOJ.3425.[POI2013]Polarization(DP 多重背包 二进制优化)
- [转]windows环境下使用virtualenv对python进行多版本隔离
- python3 urllib模块使用
- 【jsp】Servlet与jsp之间的传值