HDU2110+母函数

 /*
母函数(生成函数)
题意:
有n种资产,每种资产num份,每份有val的价值
问取出总价值的1/3有多少种方案
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
using namespace std;
const int maxn = ;
int c1[ maxn ],c2[ maxn ];
int val[ ],num[ ];
int main(){
int n;
while( scanf("%d",&n)==,n ){
int sum = ;
for( int i=;i<n;i++ ){
scanf("%d%d",&val[i],&num[i]);
sum += val[i]*num[i];
}
if( sum%!= ){
printf("sorry\n");
}
else{
int aim = sum/;
memset( c1,,sizeof( c1 ) );
memset( c2,,sizeof( c2 ) );
for( int i=;i<=val[]*num[];i+=val[] ){
c1[ i ] = ;
}//
for( int i=;i<n;i++ ){
for( int j=;j<=aim;j++ ){
for( int k=;(k+j<=aim)&&(k<=val[i]*num[i]);k+=val[i] ){
c2[ k+j ] = c1[ j ]+c2[ k+j ];
c2[ k+j ] %= ;
}
}//
for( int j=;j<=aim;j++ ){
c1[j] = c2[j];
c2[j] = ;
}//滚动数组
}
if( c1[aim]!= ) printf("%d\n",c1[aim]);
else printf("sorry\n");
}
}
return ;
}
上一篇:MySQL Cluster初步测试结果汇总图示报告 --> 用mysqlslap与sysbench进行测试


下一篇:51nod 1103 N的倍数