这篇博客是从旧博客 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;
}
}