首页 > 其他 > 详细

hust 1422 Candy!

时间:2014-05-19 22:36:33      阅读:543      评论:0      收藏:0      [点我收藏+]

题目描述

 

Halloween is coming! So xiaoY has to prepare M candies to treat the neighbor kids.

When this horrible night come, There are N little children ask xiaoY for candy, and each of them has different demand. For the i-th kid, his (or her) candy must not less than Min[i], and not greater than Max[i].

 

Now xiaoY wants to know how many ways he can give out all of his candies. (in case the large answer, please tell xiaoY the answer modular 10000007)

输入

 

First line is an integer T, represents T cases followed:

N, M ---- Number of children, Number of candies.

(0<N<=20, 0<M<=10000)

Min[i], Max[i] ---- The lower bound and upper bound of I-th kid’s demand. (N lines)

(0<=Min[i] <= Max[i] <=M)

输出

Output a number W which means total different ways of handing out the candies. (% 10000007)

样例输入

2
3 5
1 2
1 2
1 2
3 6
1 2
1 2
1 2

样例输出

Case #1: 3
Case #2: 1

神一样的题目,当然是dp解决了,dp[i+j]+=dp[j],表示将i放在当前的人,j给i前面的人,很好理解吧!我9000多ms过的,当然还有16ms过的,膜拜
bubuko.com,布布扣
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10000+10;
const int mod=10000007;

int f1[maxn],f2[maxn];

int main()
{
    int t,n,m,a,b,MAX;
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        scanf("%d%d",&n,&m);
        scanf("%d%d",&a,&b);
        for (int i=a;i<=b;i++) f1[i]=1;
        MAX=b;
        for (int k=2;k<=n;k++)
        {
            scanf("%d%d",&a,&b);
            for (int i=0;i<=MAX && i<=m;i++)
            {
                for (int j=a;i+j<=m && j<=b;j++)
                {
                    f2[i+j]+=f1[i];
                    f2[i+j]=f2[i+j]%mod;
                }
            }
            MAX+=b;
            for (int i=0;i<=MAX && i<=m;i++)
            {
                f1[i]=f2[i];
                f2[i]=0;
            }
        }
        printf("Case #%d: %d\n",tt,f1[m]%mod);
    }
    return 0;
}
bubuko.com,布布扣

 

hust 1422 Candy!,布布扣,bubuko.com

hust 1422 Candy!

原文:http://www.cnblogs.com/chensunrise/p/3731360.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!