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;}