异想天开

What's the true meaning of light, Could you tell me why

最小m段和问题

日期:2014-05-03 18:07:32
  
最后更新日期:2014-05-03 18:08:05
描述:
给定n个整数组成的序列a[1],a[2],...,a[n],编程计算该序列的最优m段分割,使m段子序列的和的最大值达到最小。输入的第1行中有2个正整数n和m。正整数n是序列的长度;正整数m是分割的段数。
解:
sum为求和函数,min为求最小值函数。定义f(u,r)表示在a[1]到a[u]的序列,r段分隔和的最大值的最小值。g(k,v)表示a[k]后v个数的和即a[k]+...+a[k+v-1],v等于1时为a[k]。
m=1时,那么a[1]+...+a[n]即为答案。 m=2时:
若n=2,则为,min{a[1],a[2]}。
若n=3,则为min{a[1],a[2]+a[3]}或min{a[1]+a[2],a[3]}选择一个小的。
...
m=3时:
若n=3,则为min{a[1],a[2],a[3]}
若n=4,则为min{a[4],f(3,2)},min{a[4]+a[3],f(2,2)}}
那么,出现子问题后,将上诉归纳起来:
answer=min{ min{g(n,1),f(n-1,m-1)} , min{g(n-1,2),f(n-2,m-1)} ,... ,min{g(m,n-m+1),f(m-1,m-1)} }