# [计数dp] ural 1114. Boxes

http://acm.timus.ru/problem.aspx?space=1&num=1114

## 1114. Boxes

Time limit: 0.6 second

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.

### Input

Input contains one line with three integers NA 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  (

Difficulty: 194    Printable version    Submit solution    Discussion
(29)

n<=20 a,b<=15

dp[i][j][k]:表示1~i个盒子中放了j个A球,k个B球的总的种数。

```//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define ull unsigned long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
using namespace std;

#define Maxn 22

ull dp[Maxn][Maxn][Maxn];
int n,a,b;

void init()
{
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;

for(int i=1;i<=20;i++)
{
for(int j=0;j<=15;j++)
{
for(int k=0;k<=15;k++)
{

for(int jj=0;jj<=j;jj++)
for(int kk=0;kk<=k;kk++)
dp[i][j][k]+=dp[i-1][jj][kk];

}
}
}

}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
init();

while(~scanf("%d%d%d",&n,&a,&b))
{
//printf("%I64d\n",dp[n][a][b]);
ll ans=0;

for(int i=0;i<=a;i++)
for(int j=0;j<=b;j++)
ans+=dp[n][i][j];
printf("%I64u\n",ans);

}

return 0;
}
```

[计数dp] ural 1114. Boxes,布布扣,bubuko.com

## Ural 1114 Boxes

Boxes Time Limit: 600ms Memory Limit: 16384KB This problem will be judged on Ural. Original ID: 111464-bit integer IO format: %lld      Java class name: (Any) N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤

## HDU4901 The Romantic Hero 计数DP

2014多校4的1005 题目:http://acm.hdu.edu.cn/showproblem.php?pid=4901 The Romantic Hero Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 393    Accepted Submission(s): 150 Problem Description There i

## CodeForces 176B Word Cut （计数DP）

Word Cut Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 176B Description Let's consider one interesting word game. In this game you should transform one word into another through specia

## (树形DP) ural 1018

1018. Binary Apple Tree Time limit: 1.0 secondMemory limit: 64 MB Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enu