HDOJ Fruit 2152【親関数】

Fruit
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3899    Accepted Submission(s): 2217
Problem Description
またたく間に収穫の季節になって、TTの専門の指導があるため、Leleは大豊作を獲得しました.特に果物、Leleは全部でN種類の果物を植えて、りんご、梨、バナナ、スイカがあります......味がおいしいだけではなくて、様子は更にきれいです.
そこで、多くの人々が名を慕って来て、Leleを探して果物を買いました.
有名なHDU ACM総教頭lcyまで来た.lcyは100元札を投げて、「M個の果物からなる果物の盛り合わせを買いたいのですが、私には小さな要求があります.果物ごとに、個数に制限があります.特定の値よりも少なくても、特定の値よりも大きくてもいけません.そして、同じ盛り合わせを2つは要りません.あなたは勝手に組み合わせて、あなたはいくつかの異なる案を組み合わせることができて、私は何部買いますか?」
今、Leleを手伝ってもらい、lcyにどれだけの果物の盛り合わせが売れるか計算してあげましょう.
注意、果物は1つを基本単位とし、これ以上分けることはできません.2つのスキームについて、各果物の数が同じであれば、この2つのスキームは同じであると考えられる.
結局Leleはこのお金をもらって、また彼の学業を続けることができます～
 
Input
この問題には複数のテストが含まれています.ファイルの終了(EOF)まで処理してください.
各グループのテストの最初の行は2つの正の整数NとMを含む(意味は問題の説明を参照して、0次にN行の果物の情報があって、1行ごとに2つの整数A,B(0<=A<=B<=100)は、少なくともこの果物A個を買う必要があることを示して、せいぜいこの果物B個しか買えない.
 
Output
各グループのテストについて、合計で販売できるシナリオ数を1行に出力します.
タイトルデータはこの答えが10^9未満であることを保証します.
 
Sample Input

   
   
   
   

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

 
Sample Output

   
   
   
   

    
    
    
    2
12
   
   
   
   

 
Author
Linle
 
Source
ACMプログラミング期末試験——2008-01-02(3教417)
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1171  1709  2110  2079  2189 
 
 注意値範囲を初期化します.

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int c1[10010];
int c2[10010];
int N,M;

struct Num{
	int x,y;
}num[10010];

int Max,Min,Maxn;

int generation()
{
	memset(c1,0,sizeof(c1));
	memset(c2,0,sizeof(c2));
	for(int i=num[1].x;i<=num[1].y;i++){
		c1[i]=1;
	}
	for(int i=2;i<=N;i++){
		for(int j=0;j<=M;j++){
			for(int k=num[i].x;k+j<=M&&k<=num[i].y;k++)
			c2[j+k]+=c1[j];
		}
		for(int j=0;j<=M;j++){
			c1[j]=c2[j];
			c2[j]=0;
		}
	}
	return c1[M];
}

int main()
{
	while(scanf("%d%d",&N,&M)!=EOF){
		Maxn=0;
		for(int i=1;i<=N;i++){
			scanf("%d%d",&num[i].x,&num[i].y);
		}
		printf("%d
",generation());
	}
	return 0;
}