假设有一个数组:
int x[102];
int sum;相邻三列的和;
int selector;
爬梯总高度height=0;
先扫描一边输入,让x[i]的值 为 列i的 最高物品高度,注意索引0和索引101的位置存为0,架子在1到100之间的索引。
当前最大值:
int current_max=0;
while(1)
{
for(j=1;j<=100;j++)
{
if (x[j]>current_max) current_max=x[j], current_index=j;
}
if(current_max==0) break;
我们遍历最大值附近的三列,看从哪里爬最佳。
sum=0;
for(j=current_index-1; j<=current_index+1;j++)
{
if(x[j-1]+x[j]+x[j+1]>sum) selector=j,sum= x[j-1]+x[k]+x[k+1];
}
height += x[current_index]; 我们决定在selector列爬梯。爬梯高度是current_index列的高度。
x[selector-1] = x[selector] = x[selector+1]=0; 这个时候这列附近的数据对下次的判断已经不具有参考意义。所以清掉它们。
}
然后输出结果:
printf("%d\n", height);
考虑一些特殊情况,比如输入使得所有x[i]均相等,代码是否能适应等。以上为大体思路,供楼主参考。没有测试过,不一定对。因为没有证明这样选是整体最优解。
[[it] 本帖最后由 hoodlum1980 于 2008-10-12 12:30 编辑 [/it]]