数论吧 关注:13,624贴子:76,893
  • 2回复贴,共1

一个离散最值问题

只看楼主收藏回复

a1a2+a2a3+a3a4+a4a5+a5a6+a6a7+a1+2a7的最小值,其中ai,i=1,2,...,7是3,4,5,6,7,8,9的一个排列.


IP属地:江苏1楼2024-05-08 19:12回复
    不妨设a[8]=2, a[9]=1,式子加上2变成∑a[i]a[i+1],i=1~9,其中a[10]=a[1]
    式子取最小值的一个必要条件是,如果存在1≤i<j≤7且a[i]<a[j],则a[i-1]>a[j+1]
    如果存在1≤i<j≤7且a[i]>a[j],则a[i-1]<a[j+1]
    (当i=1时a[i-1]=a[9])
    否则如果存在1≤i<j≤7,使a[i]<a[j]且a[i-1]<a[j+1]
    只要把a[i]~a[j]倒序排列,其他不变,式子的值改变了
    a[i]a[j+1]+a[j]a[i-1]-a[i]a[i-1]-a[j]a[j+1] = (a[i]-a[j])(a[j+1]-a[i-1])<0
    得到更小的取值
    同理也不会出现1≤i<j≤7,a[i]>a[j]且a[i-1]>a[j+1]
    因此,由于a[0]=a[9]=1小于a[1]~a[8]的所有数,a[1]必须大于a[2]~a[7]的所有数,只能等于9
    同样a[8]小于a[1]~a[7]的所有数,a[7]必须大于a[2]~a[6]的所有数,只能等于8
    接下来由于a[1]大于a[2]~a[8],所以a[2]小于a[3]~a[7],只能等于3
    a[7]大于a[2]~a[6],所以a[6]小于a[3]~a[5],只能等于4
    依次可得
    a[1]~a[7]= {9, 3, 7, 5, 6, 4, 8}
    此时式子的值等于27+21+35+30+24+32+9+16=194


    IP属地:北京来自Android客户端3楼2024-05-09 09:04
    回复
      如果我没理解错的话,这应该是个整数规划问题,只是约束条件有些特别,拓展一下,本题也应该有个最大值268。


      IP属地:上海来自Android客户端4楼2024-05-09 15:05
      回复