思路是：用动态规划求出每个“城堡”可能的高度，最后扫描一遍即可。意思就是如果对于前k-1层，如果高度h是可能的，那么对于前k层，h+a[k]是可能的。注意要先求出初始高度最小的那个城堡高度min，因为最终高度比min还高是不可能的，这样可以提高效率，减少递推量。一开始循环的顺序写反了，只得了70分，自己感觉能得70运气还是不错的了……
以下是我的代码（没有秒杀，660ms）：
#include<stdio.h>
long n,min,find,a[101][101]=
{0},sum[101]={0},d[101][10001]={0};
void init()
{
long i,tmp;
scanf("%ld",&n);
min=200000000;
find=0;
for(i=1;i<=n;i++)
{
scanf("%ld",&tmp);
while(tmp!=-1)
{
a[i][0]++;
a[i][a[i][0]]=tmp;
sum[i]+=tmp;
scanf("%ld",&tmp);
}
if(sum[i]<min) min=sum[i];
}
}
void work()
{
long i,j,k;
for(i=1;i<=n;i++)
d[i][0]=1;
for(k=1;k<=n;k++)
{
for(i=1;i<=a[k][0];i++)
for(j=min;j>=0;j--)
if(j-a[k][i]>=0&&d[k][j-a[k][i]]==1)
d[k][j]=1;
}
for(i=min;i>=1;i--)
{
for(j=1;j<=n;j++)
if(d[j][i]!=1)
break;
if(j==n+1)
{
printf("%ld\n",i);
return;
}
}
printf("%ld\n",0);
}
int main()
{
init();
work();
return 0;
}
posted on 2010-01-06 20:29
lee1r 阅读(437)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划