思路是：用動態規劃求出每個“城堡”可能的高度，最后掃描一遍即可。意思就是如果對于前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 閱讀(442)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃