Ural 1114 Boxes

Boxes

Time Limit: 600ms

Memory Limit: 16384KB

This problem will be judged on Ural. Original ID: 1114
64-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 ≤ 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

2 1 1

Sample Output

9

Source

First competition for selecting the Bulgarian IOI team.

解题:强行dp

$dp[i][j][k]表示前i个盒子放了j个红球k个蓝球的方案数$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 21;
 4 unsigned long long dp[maxn][maxn][maxn];
 5 int main() {
 6     int N,A,B;
 7     while(~scanf("%d%d%d",&N,&A,&B)) {
 8         memset(dp,0,sizeof dp);
 9         dp[0][0][0] = 1;
10         for(int i = 1; i <= N; ++i)
11             for(int j = 0; j <= A; ++j)
12                 for(int k = 0; k <= B; ++k)
13                     for(int a = 0; a <= j; ++a)
14                         for(int b = 0; b <= k; ++b)
15                             dp[i][j][k] += dp[i-1][a][b];
16         unsigned long long ret = 0;
17         for(int i = 0; i <= A; ++i)
18             for(int j = 0; j <= B; ++j)
19                 ret += dp[N][i][j];
20         printf("%I64u\n",ret);
21     }
22     return 0;
23 }

时间: 09-27

Ural 1114 Boxes的相关文章

[计数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 blu

组合数取模(转载)

本文转自:http://blog.csdn.net/skywalkert/article/details/52553048 0. 写在前面 在程序设计中,可能会碰到多种类型的计数问题,其中不少涉及到组合数的计算,所以笔者写下这么一篇文章,期望能解决一些常规的组合数求模问题.以下部分内容改编自AekdyCoin的<组合数求模>,而且为了感谢他对(懵懂的)笔者的启发,这篇文章的标题与其文章相同.另外,感谢Picks将多项式运算的技巧在中国进行推广,感谢51nod提供了许多有趣的数论题目,感谢fot

Ural 1081 Binary Lexicographic Sequence(DP)

题目地址:Ural 1081 先用dp求出每个长度下的合法序列(开头为1)的个数.然后求前缀和.会发现正好是一个斐波那契数列.然后每次判断是否大于此时长度下的最少个数,若大于,说明这一位肯定是1,若小于,则肯定是0.就这样不断输出出来即可. 代码如下: #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #in

HDU 1114 (dp 完全背包)

鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 Problem Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The i

URAL 1684. Jack&#39;s Last Word KMP

题目来源:URAL 1684. Jack's Last Word 题意:输入a b 把b分成若干段 每一段都是a的前缀 思路:b为主串 然后用a匹配b 记录到b的i位置最大匹配的长度 然后分割 分割的时候要从后往前 如果a = abac b = abab 那么如果从前往后 首先覆盖了aba 然后b就不能覆盖了 从后往前就可以了 首先覆盖ab 下一次还是ab 因为已经记录了到i位置的最大匹配长度 根据长度从末尾倒退 每次倒退的时候只要是最大的匹配的长度 因为如果在某一次的递推 记录的最大匹配的前缀

uva 12657 - Boxes in a Line(AC和TLE的区别,为什么说STL慢..)

用STL中的list写的,TLE #include<cstdio> #include<iostream> #include<cstring> #include<list> #include<algorithm> using namespace std; list<int> l; list<int>::iterator it1,it2,it3,it4,it5,it; void work(int a,int a1=1,int

[LeetCode] Remove Boxes 移除盒子

Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes

[2016-03-27][HDU][1114][Piggy-Bank]

时间:2016-03-27 16:37:56 星期日 题目编号:[2016-03-27][HDU][1114][Piggy-Bank] 遇到的问题:注意f == e的情况,即dp[0] = 0; #include <cstring> #include <cstdio> #include<algorithm> using namespace std; int dp[10000 + 10]; int w[500 + 10],c[500 + 10]; int main(){

ural 1272. Non-Yekaterinburg Subway

1272. Non-Yekaterinburg Subway Time limit: 1.0 secondMemory limit: 64 MB A little town started to construct a subway. The peculiarity of the town is that it is located on small islands, some of them are connected with tunnels or bridges. The mayor is