【hdoj_2152】Fruit(母函数)

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

本题采用母函数模板求解,母函数模板如下:

http://blog.csdn.net/ten_sory/article/details/59483762

本题中的价值v[i]均为1,s[i]=A[i],e[i]=B[i],套用上述模板,容易求解.

C++代码如下:

#include<iostream>
using namespace std; int main()
{
int N,M;
while(cin >> N >> M)
{
int *A = new int[N+1];
int *B = new int[N+1];
int i,j,k;
int sum = 0;
for(i=1;i<=N;i++)
{
cin >> A[i] >> B[i];
sum += 1*B[i];
}
if(sum<M)//如果水果总数<对方要买的数量,退出
{
cout << 0 << endl;
continue;
} int *a = new int[M+1];
int *b = new int[M+1];
for(i=0;i<=M;i++)
{
a[i] = 0;
b[i] = 0;
}
a[0] = 1;
for(i=1;i<=N;i++)
{
for(j=A[i];j<=B[i] && j*1<=M;j++)
for(k=0;k+j*1<=M;k++)
b[k+j*1]+=a[k]; for(k=0;k<=M;k++)
{
a[k] = b[k];
b[k] = 0;
}
}
cout << a[M] << endl; } return 0;
}

上述代码,提交可以通过.

上一篇:掌握numpy(一)


下一篇:排列组合 HDU - 1521 -指数型母函数