原谅我再发一次。
终于ac了。。。
在学校的时候这个题得了90分~回家后改了一个地方 就ac了~
这种心情难以言语~我知道你看到这个题一定很鄙视我。。很简单~搜索就能过的传说中的dp~
第一次看完这个题 用了10多分钟就写完了这个程序段~可是调试卡了5节课~~~
就因为 理解错了题目~
前后 用搜索写了一次 用dp写了一次。~~还找大牛帮忙~盯着一个题 从头到尾 想为什么会错~
用各种方式~改各种有可能出现的错误~甚至还改了初始化~
算是个教训~贴在这里~恩 细节~~~
我会记住这个题~当我在不能ac的时候~看到这个 提醒我 要注意细节~
我可以忍耐着调了5节课~~也算是一大进步吧。以前总是放弃的~
恩 总之 这种终于ac的感觉 ~如果不是真正经历过 很难体会的~
成就感~高兴地要蹦起来了呢~~呵呵~~
呵呵虽然 算是勉强通过把~~时间复杂度比较高~不过。。恩~ac就好~~
#include<stdio.h>
int a[101][10001]={};
int f[101][10001]={};
long sum[101]={};
int main()
{ int i=0,j=0,n=0,s=0,x=0,min=32767,h=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i][0]=1;
for(i=1;i<=n;i++)
{ sum[i]=0;
scanf("%d",&x);
while(x!=-1)
{ for(j=sum[i];j>=0;j--)
{ if(a[i][j]==1)
a[i][j+x]=1;
}
sum[i]+=x;
scanf("%d",&x);
}
if(sum[i]<min) min=sum[i];
}
for(i=1;i<=sum[1];i++)
f[1][i]=a[1][i];
for(i=2;i<=n;i++)
{ for(j=1;j<=min;j++)
{ if((f[i-1][j]==1)&&(a[i][j]==1))
f[i][j]=1;
}
}
for(i=1;i<=min;i++)
{if(f[n][i]==1) h=i;}
printf("%d",h);
return 0;
}