Question

poj1742 在VC6++上运行没问题，提交的时候提示Compile Error，大神能帮我看下吧，谢谢哈，感激不尽~~

#include<stdio.h>
#include<string.h>
_int64 c1[100010],c2[100010];
int main()
{
_int64 a[110],c[110],n,m,i,j,k,count;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
if(m==0&&n==0)
break;
for(i=0;i<n;i++)
scanf("%I64d",&a[i]);
for(i=0;i<n;i++)
scanf("%I64d",&c[i]);
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(i=0;(i<=m)&&(i/a[0]<=c[0]);i+=a[0])
c1[i]=1;
for(i=1;i<n;i++)
{
for(j=0;j<=m;j++)
for(k=0;(k+j<=m)&&(k/a[i]<=c[i]);k+=a[i])
c2[j+k]+=c1[j];
for(j=0;j<=m;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
count=0;
for(i=1;i<=m;i++)
if(c1[i])
count++;
printf("%I64d\n",count);
}
return 0;
}
http://poj.org/problem?id=1742

Answer 1

现在来简单说一下你的程序的问题，编译错误的原因应该是POJ的编译器不支持_int64的原因，改为long long就可以了，格式控制符为lld。还有就是搞ACM用VC是一大忌，使用VC你会在以后你可能在比赛和学习中吃很大的亏。因为很多VC承诺的东西ACM认可的GCC和G++编译器都没有承诺。建议使用code blocks。还有就是修改完之后发现你的代码超时了，你仔细检查一下你的算法吧。如果对这道题算法有疑问，欢迎追问。

追问

谢谢哈O(∩_∩)O
果然是超时了。。。我用母函数做的。。网上好像很多都是用背包做的，不过那个我还没学。。
大神有办法优化吧？
可加QQ谈否?

追答

母函数我不会，看到这道题第一个就想到01背包，而且这道题是很典型的01背包问题，时间复杂度是n的平方

追问

哦哦~~那我在去看下那01背包的，谢啦O(∩_∩)O~

追答

其实你最好还是把背包九讲想看一下吧

追问

嗯，好的。

追答

你看看我在百度Hi上给你的留言吧

Answer 2

报的什么错？ 可能是_int64的问题，改成long long 试试看。

追问

en,long long用G++提交就不会了。不过超时了。谢谢O(∩_∩)O哈！

Answer 3

#include<stdio.h>
#include<string.h>
int cc[100010];
int main()
{
int m,n;
int a[110],c[110],i,j,k,t,count;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==0&&n==0)
break;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
scanf("%d",&c[i]);
memset(cc,0,sizeof(cc));
for(i=0,t=0;i<=m&&t<=c[0];i+=a[0],t++)
cc[i]=1;
for(i=1;i<n;i++)
{
for(j=m;j>=0;j--)
{
if(cc[j])
for(k=a[i],t=1;k+j<=m&&t<=c[i];k+=a[i],t++)
{
if(cc[j+k])
break;
cc[j+k]=1;
}
}
}
count=0;
for(i=1;i<=m;i++)
if(cc[i])
count++;
printf("%d\n",count);
}
return 0;
}

追问

这有用到什么算法吗，我这菜鸟看不懂~。。~大神能否写下注释?谢谢哈~

追答

这样会不会好理解一些？
#include
#include
int c1[100010];
int main()
{
int a[110],c[110],n,m,i,j,k,t,count;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==0&&n==0)
break;
for(i=0;i=0;j--)
if(c1[j])
for(k=a[i],t=1;(k+j<=m)&&(t<=c[i])&&c1[j+k]==0;k+=a[i],t++)
c1[j+k]=1;
}
count=0;
for(i=1;i<=m;i++)
if(c1[i])
count++;
printf("%d\n",count);
}
return 0;
}