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

hide tags for unsolved problems
)

Difficulty: 194    Printable version    Submit solution    Discussion
(29)

My submissions    All submissions (7145)    All
accepted submissions (2115)
    Solutions rating (1803)

题目意思:

有n个盒子,有相同的A球a个,相同的B球b个,每个盒子可以不放球可以放多个球,球可以不全放完。求放的种数。

n<=20 a,b<=15

解题思路:

简单计数dp

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

显然dp[i][j][k]=∑(dp[i-1][jj][kk]) (jj<=j,kk<=k)

注意要用usigned long long不然最后一个会超

代码:

//#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
//#pragma comment(linker, "/STACK:1024000000,1024000000")
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

时间: 05-07

[计数dp] ural 1114. Boxes的相关文章

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 ≤

HDU4815/计数DP

题目链接[http://acm.hdu.edu.cn/showproblem.php?pid=4815] 简单说一下题意: 有n道题,每到题答对得分为a[ i ],假如A不输给B的最小概率是P,那么A最少要得到多少分. 解题过程: 假设有n道题,每个题有两个状态,胜或者败,假设达到某个分数m有k(计数DP)种方式,那么最后是这个分数的概率是k/pow(2,n).那么A不输给B的概率就是小于等于m的分数的概率和. #include<bits/stdc++.h> const int maxn =

[sdut]2879计数dp……或者递推

第五届省赛C:colourful cupcakes N=60. 天真如我,居然在考虑搜索的算法/(ㄒoㄒ)/~~三叉树……3^60=10^24+……不计算考虑复杂度都是耍流氓>_< 再算了一下,感觉O(N^4)可以试试,60^4=10^8+……但是毕竟最差的情况嘛>_<,再看一下题解果然是4重循环的……计数……dp……(想到之前坚信的搜索不禁(*/ω\*)) 中间看到了一个三次动规六个方程的算法. 做麻烦了. 学长思路好快. #include<iostream> #in

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

ACM/ICPC算法训练 之 数学很重要-浅谈“排列计数” (DP题-POJ1037)

这一题是最近在看Coursera的<算法与设计>的公开课时看到的一道较难的DP例题,之所以写下来,一方面是因为DP的状态我想了很久才想明白,所以借此记录,另一方面是看到这一题有运用到 排列计数 的方法,虽然排列计数的思路简单,但却是算法中一个数学优化的点睛之笔. Poj1037  A decorative fence 题意:有K组数据(1~100),每组数据给出总木棒数N(1~20)和一个排列数C(64位整型范围内),N个木棒长度各异,按照以下条件排列,并将所有可能结果进行字典序排序 1.每一

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

递推DP URAL 1031 Railway Tickets

题目传送门 1 /* 2 简单递推DP:读题烦!在区间内的都更新一遍,dp[]初始化INF 3 注意:s1与s2大小不一定,坑! 4 详细解释:http://blog.csdn.net/kk303/article/details/6847948 5 */ 6 #include <cstdio> 7 #include <iostream> 8 #include <algorithm> 9 #include <cstring> 10 #include <s

记忆化搜索(DFS+DP) URAL 1501 Sense of Beauty

题目传送门 1 /* 2 题意:给了两堆牌,每次从首部取出一张牌,按颜色分配到两个新堆,分配过程两新堆的总数差不大于1 3 记忆化搜索(DFS+DP):我们思考如果我们将连续的两个操作看成一个集体操作,那么这个操作必然是1红1黑 4 考虑三种情况:a[]连续两个颜色相同,输出11:b[]连续两个相同,输出22: 5 a[x] != b[y], 输出12:否则Impossible 6 详细解释:http://blog.csdn.net/jsun_moon/article/details/10254