读书人

hdu 1171用雌函数做的一直wa测试

发布时间: 2012-08-21 13:00:21 作者: rapoo

hdu 1171,用母函数做的,一直wa,测试的数据都对啊
#include<iostream>
using namespace std;
struct node{
int value;
int num;
}a[55];

int main()
{ int c1[100000],c2[100000];
int n,i,j,k,max1,mid;
while(scanf("%d",&n))
{ max1=0;
if(n<0)break;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].value,&a[i].num);
max1+=a[i].value*a[i].num;
}
mid=max1/2;

for(i=0;i<=max1;i++)
{
c1[i]=0;
c2[i]=0;
}
for(i=0;i<=a[1].value*a[1].num;i+=a[1].value)
c1[i]=1;

int b=0;
for(i=2;i<=n;i++)
{
b+=a[i-1].value*a[i-1].num;
for(j=0;j<=b;j++)
{
for(k=0;k<=a[i].value*a[i].num;k+=a[i].value)
{
c2[k+j]+=c1[j];
}
}
for(j=0;j<=b+a[i].value*a[i].num;j++)
{c1[j]=c2[j];
c2[j]=0;
}
}
for(i=mid;i>=0;--i)
{
if(c1[i]!=0)
{
printf("%d %d\n",max1-i,i);
break;
}
}

}
return 0;
}


[解决办法]
int c1[100000],c2[100000];
改为
static int c1[250000],c2[250000];
可AC。因为3个参数(N,V,M)的最大值相乘后是250000,而100000不够大。
[解决办法]
大数组的话 还是放到函数外面声明吧。
stack空间有限啊
[解决办法]
对数组开小了,楼上说的都对,发个参考:

C/C++ code
#include"stdio.h"int c1[260000];int main(){    int N,i,j,k,max,mid,s;    int w[51],num[51];    while(scanf("%d",&N)&&N>0)    {        max=0;        for(i=0;i<N;i++)        {            scanf("%d%d",&w[i],&num[i]);            max=max+w[i]*num[i];        }        mid=max/2;        for(i=0;i<=mid;i++)            c1[i]=0;        for(i=0;i<=num[0];i++)            c1[i*w[0]]=1;        for(i=1;i<N;i++)        {            for(j=0;j<=mid;j++)            {                if(c1[j]==0)                    continue;                for(k=0,s=0;s<=num[i]&&k+j<=mid;k+=w[i],s++)                    c1[k+j]=1;            }        }        for(i=mid;i>=0;i--)            if(c1[i]!=0)                break;            printf("%d %d\n",max-i,i);    }    return 0;} 

读书人网 >C++

热点推荐