FruitWorm


Description

title: Fruit

自见识了平安夜苹果的涨价后,Lele就以外家门口水平种了相同排苹果树,共有N棵。 

tags: [acm,杭电,母函数]

题目链接

Problem Description

时而到了收获的季节,由于生TT的正规指导,Lele获得了要命丰收。特别是鲜果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道鲜美,样子更好看。
遂,很多人们向往而来,找Lele买水果。
还连知名的HDU ACM总教头 lcy
也来了。lcy抛来同从百元大钞,”我要进由M个水果做的鲜果拼盘,不过自己有个不大要求,对于每种水果,个数上自出限量,既未可知简单某个特定值,也不能够超出某个特定值。而且我毫不简单份一样的拼盘。你随便搭配,你可知组发小种不同的方案,我便市多少份!”
今日就呼吁您拉拉Lele,帮他好不容易一好不容易到底会卖起些许份水果拼盘给lcy了。
在意,水果是以单吗着力单位,不克再分开。对于有数栽方案,如果各种水果之数据还同,则当当下片种方案是一模一样之。
末Lele拿了这笔钱,又足以持续他的作业了~

 

Input

遵照题目包含多组测试,请处理到文件截止(EOF)。
每组测试第一实施包括个别单刚整数N和M(含义见题目叙述,0<N,M<=100)
连通下去有N行水果之音,每行两只整数A,B(0<=A<=B<=100),表示至少要进该水果A个,至多只能请该水果B个。

 

Output

于每组测试,在一行里输出总共会卖的方案往往。
题材数据保证这答案小于10^9

 

Sample Input

2 3
1 2
1 2
3 5
0 3
0 3
0 3

 

Sample Output

2
12

忽Lele发现于左起第P株树上(从1初步计数)有一致长达毛毛虫。为了见到毛毛虫变蝴蝶的历程,Lele在苹果树旁观察了生悠久。虽然尚未见到蝴蝶,但Lele发现了一个法则:每过1分钟,毛毛虫会轻易从同棵树爬至隔壁之同蔸树上。 

分析

抑或母函数题材,只是多矣有限量,稍微处理部分尽管尽了。

遵照刚起毛毛虫在第2株树上,过1分钟后,毛毛虫可能会见于第1棵树上或者第3蔸树上。如果正好起经常毛毛虫在第1株树上,过1分钟以后,毛毛虫一定会在第2蔸树上。 

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        vector<int>sum, value, a, b;
        for (int i = 0; i < n; i++)
        {
            int a1, b1;
            scanf("%d%d", &a1, &b1);
            a.push_back(a1);//最低限制
            b.push_back(b1);//最高限制
        }
        int c1[10050] = {0}, c2[10050] = {0};
        for (int i = a[0]; i <= b[0]; i++)//不再是从零开始了
            c1[i] = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= m; j++)
                for (int k = a[i]; k + j <= m && k <= b[i]; k++)
                    c2[k + j] += c1[j];
            for (int i = 0; i <= m; i++)
            {
                c1[i] = c2[i];
                c2[i] = 0;
            }

        }
        printf("%d\n", c1[m]);
    }
    return 0;
}
/*
2 3
1 2
1 2
3 5
0 3
0 3
0 3
*/

当今晓您苹果树的数目N,以及毛毛刚开始所于的位置P,请问,在M分钟后,毛毛虫到达第T棵树,一共发微种行动方案往往。 

 

Input

按部就班题目包含多组测试,请处理到文件截止(EOF)。 
每组测试占一执行,包括四独正整数N,P,M,T(含义见题目叙述,0<N,P,M,T<100) 

 

Output

对每组数据,在一行里输出一共的方案往往。 
题目数据保证答案小于10^9 

 

Sample Input

3 2 4 2

3 2 3 2

 

Sample Output

4

0

Hint

 第一组测试中有以下四种走法: 2->1->2->1->2 2->1->2->3->2 2->3->2->1->2 2->3->2->3->2 





#include<stdio.h>
#define N 110
int Slove(int n,int p,int m,int t)
{
    int i, j;
    int dp[N][N] = {0};

    dp[0][p] = 1;

    for(i=1; i<=m; i++)
    {
        for(j=1; j<=n; j++)
        {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
        }
    }
    return dp[m][t];
}

int main()
{
    int n, p, m, t;

    while(scanf("%d%d%d%d", &n, &p, &m, &t)!=EOF)
    {
        int ans;
        ans = Slove(n,p,m,t);
        printf("%d\n", ans);
    }
    return 0;
}

 

相关文章