假设有一个木棍序列N,其长度分别为a1,a2,…aN。定义该序列的质量为
F(N)= |a-b|+|b-c|+|c-d|。
有个工厂老板找一批木棍，先后去了几个木材厂，都能够提供m个木棍。于是他就想从这么多木棍中找出一个木棍序列N,使得F（N）最小。但让他有个要求：
1 每个厂家只取一个木棍
2 每个厂家都有一个编号1-n,取木棍的顺序是按厂家编号进行。
输入：
包含多个测试用例，对每个测试用例，第一行包含两个整数n, m (1 <= n, m <= 1000)。 接下来的n行，每行包含m个数据，表示第n-1个厂家的m个木棍长度。处理到文件结束为止
输出：
对每个测试用例，在一行中输出F（N）的最小值
样例输入：
3 3
2 3 1
4 7 6
7 9 2
样例输出
3
提示：满足条件的木棍序列式3 4 2。第一个厂家选3 第二个厂家选4 第三个厂家选2
因为每行的取法只于上一列有关系！！！
那么可以一层一层的找。。。
但是为什么就错了呢？？？
题解用到了STL中的东西。。。
关于这个函数的具体用法：
函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
举例如下：
一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标
则
pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。
pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。
所以，要记住：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！~
返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置
摘自：http://blog.csdn.net/niushuai666/article/details/6734403
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 #define inf 1<<30 9 int n,m,cap[1010][1010]; 10 int Min[1010][1010]; 11 int main() 12 { 13 int i,j; 14 while(scanf("%d%d",&n,&m)!=EOF) 15 { 16 for(i=0;i<n;i++) 17 { 18 for(j=0;j<m;j++) 19 scanf("%d",&cap[i][j]); 20 sort(cap[i],cap[i]+m); 21 } 22 memset(Min,0,sizeof(Min)); 23 for(i=1;i<n;i++) 24 { 25 for(j=0;j<m;j++) 26 { 27 Min[i][j]=inf; 28 int temp=lower_bound(cap[i-1],cap[i-1]+m,cap[i][j])-cap[i-1]; 29 if(temp<m) 30 Min[i][j]=min(Min[i][j],Min[i-1][temp]+abs(cap[i-1][temp]-cap[i][j])); 31 if(temp>0) 32 Min[i][j]=min(Min[i][j],Min[i-1][temp-1]+abs(cap[i-1][temp-1]-cap[i][j])); 33 } 34 } 35 int ans=inf; 36 for(i=0;i<m;i++) 37 ans=min(ans,Min[n-1][i]); 38 printf("%d ",ans); 39 } 40 return 0; 41 }