木板长为:21
输入:
N=3
L={8,5,8}
输出:
34
由于木板的切割顺序不确定,自由度很高.首先,切割的方法可以参见二叉树,每一个叶子节点就对应了切割出的一块块木板.叶子节点的深度就对应了为了得到对应木板所需的切割次数,开销的合计就是个叶子节点的
木板的长度*节点的深度
的总和.
最短的板与次短板的节点应当是兄弟节点
1 typedef long long ll; 2 3 int N,L[MAX]; 4 5 void solve() 6 { 7 ll ans=0; 8 //直到计算到木板为1块时为止 9 while(N>1){ 10 int mii1=0,mii2=1; 11 if(L[mii1]>L[mii2]) swap(mii1,mii2); 12 13 for(int i=2; i<N; i++){ 14 if(L[i]<L[mii1]){ 15 mii2=mii1; 16 mii1=i; 17 } 18 else if(L[i]<Lmii2){ 19 mii2=i; 20 } 21 } 22 //将两块板拼合 23 int t=L[mii1]+L[mii2]; 24 ans+=t; 25 26 if(mii1 == N-1) swap(mii1.mii2); 27 L[mii1]=t; 28 L[mii2]=L[N-1]; 29 N--; 30 } 31 printf("%d\n"ans); 32 }
来自:<<挑战程序设计竞赛>>
原文：http://www.cnblogs.com/wangmengmeng/p/5226765.html