Blog·Tanky WooABOUTRSS

HDU/HDOJ 2152 Fruit(上下界母函数)

28 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2152

上下界母函数,没什么特别的,理解了母函数就可以OK~~~

母函数详解:http://www.wutianqi.com/?p=596

不过有一点要注意,我只把c2全部初始化为0,而c1我只把least和most的范围初始化为1,而忘了把其余部分初始化为0,这样就导致了一直WA~~~

AC代码:

// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Title: HDOJ 2152 Fruit
// About: 母函数

#include 
using namespace std;

int N, M;
//int A, B;
int a[105], b[105];
int c1[105], c2[105];

int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> N >> M)
    {
        //cin >> A >> B;
        for(int i=1; i<=N; ++i)
            cin >> a[i] >> b[i];
        memset(c2, 0, sizeof(c2));
        memset(c1, 0, sizeof(c1));   // 这里害我找了一个小时的错误
        for(int i=a[1];i <=b[1]; ++i)
            c1[i] = 1;
        for(int i=2; 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 j=0; j<=M; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout << c1[M] << endl;
    }
}