/***************************************************************************************************************************
题目大意:不可以用num1个1,num2个2,num3个5组合得到的最小数;
题目解析:求(1+x^eum[0]+.....+x^(num1*eum[0])(1+x^eum[1]+.....+x^(num1*eum[1]).......(1+x^eum[n-1]+.....+x^(num1*eum[n-1])
的系数为零的指数;若系数都不为零,则最小数为sum+1;
错误分析:1.不能确定j的循环次数;
2.没有把M数值开到最大,导致ACCESS_VIOLATION (由于指针、数组下标越界造成的)
3.注意循环结束条件,不要造成TLE
*********************************************************************************************************/
#include<stdio.h> #include<iostream> #define M 250002 using namespace std; int a1[M],a2[M] ; int i,j,k,num[52],c,eum[52]; /*num[i]表示i物品的件数,eum[i]表示i物品的价值*/ int main() { int n; while(scanf("%d",&n),n>0) { int s[52]={0}; scanf("%d %d",&eum[0],&num[0]); s[0]=num[0]*eum[0]; for(i=1;i<n;i++) { scanf("%d %d",&eum[i],&num[i]); s[i]=s[i-1]+num[i]*eum[i]; } for(i=0;i<s[n-1];i++) /*初始化*/ { a1[i]=a2[i]=0; } for(i=0;i<=s[0];i+=eum[0]) /*先为(1+x^eum[0]+.....+x^(num1*eum[0])的系数赋值*/ { a1[i]=1; } c=(int)(s[n-1]/2); /*因题意只需要总指数数一半就可以求出结果,所以为了减少运行时间,必须取一半;*/ for(i=2;i<=n;++i) { for(j=0;j<=s[i-1];++j) /*控制表达i的项数;当前最大指数为 s[i-1];而不用s[n-1],可减少运行时间;即j的大小不能大于前eum[i-1]的组合总数*/ for(k=0;k+j<=c&&k<=eum[i-1]*num[i-1];k+=eum[i-1]) /*指数k最大不能超过eum[i-1]*num[i-1]总数;*/ { a2[j+k]+=a1[j]; } for(j=0;j<=c;++j) { a1[j]=a2[j]; a2[j]=0; } } if(a1[c]!=0&&s[n-1]%2==0) /*若指数为c的项存在(即指数c的系数不为0),且最大指数可以被2整除,则输出两个相同的数;*/ printf("%d %d\n",c,c); else { while(a1[c--]==0); //找到指数小于c的系数不为0的数; if(c+1<s[n-1]-c-1) //判断两个数的大小; printf("%d %d\n",s[n-1]-c-1,c+1); else printf("%d %d\n",c+1,s[n-1]-c-1); } } return 0; }