关于最长递增子序列的实际应用--动态规划
参考链接：
a.http://www.programfan.com/blog/article.asp?id=13086
b.http://blog.csdn.net/hhygcy/article/details/3950158
?
1.对（http://hao3100590.iteye.com/blog/1548135）中问题6：最长递增子序列的改进，减少时间复杂度
算法的思想：
? 它不是使用的动态规划法，而是普通的算法思想，就是在数组中直接存储最长递增子序列，在循环的过程中不断的查找插入位置，直到最终找到。下面列出实现的过程：
从上面的过程可以看出该算法的实现过程，在查找sub合适插入位置的时候，使用了二分查找，提高了查找速度，这个算法本身也比前面利用动态规划法简单，但是该算法复杂之处不在算法
而在算法正确性的证明！，算法证明见：http://www.programfan.com/blog/article.asp?id=13086
代码：
?
#include <iostream>#include <cstring>using namespace std;const int MIN = -32768;/***a:原始数组*sub:最终获取的最大递增子序列（注意，sub[0]是哨兵，结果从1开始）*length :数组长度**/int longestSub(int* a, int* sub, int length){if(length<=0) return 0;sub[0]=MIN;//为了初始化的比较,相当于哨兵的作用sub[1]=a[0];//初始序列就是a[0]int len = 1;//最大递增子序列长度int mid, left, right;//二分查找时的indexfor(int i=0; i<length; i++){//在sub数组中二分查找合适的插入位置left = 0;right = len;//获取的最终插入位置就如a[i]=6,{1,3,5,7}位置就是5后面index=3，会替代7while(left<=right){mid = (left+right)/2;if(sub[mid]<a[i]) left=mid+1;else right=mid-1;}//策略是使用替代，不断的寻找合适的值，插入sub，最后sub中剩余的值就是要寻找的最长递增子序列sub[left]=a[i];if(left>len) len++;}return len;}int main(){int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }; int* sub = new int[13];memset(sub,0,sizeof(int));int length = longestSub(a,sub,13);cout<<"length:"<<length<<endl;for(int i=1; i<=length; i++) cout<<sub[i]<<" ";delete[] sub;sub=NULL;return 0;}?
?这个算法的时间复杂度只有O(nlogn)，效率明显提高了而且也更简单了
不过其结果和改进之前的有些不同，前面是{1,3,4,5,6,19}，改进之后是{1,3,4,5,6,7}结果都是正确的！
?
2.实际应用的两个例子
a.造桥问题
问题描述：
要在一条河的南北两边的各个城市之间造若干座桥．桥两边的城市分别是a(1)...a(n)和b(1)...b(n).这里的要求a(i)只可以和b(i)之间造桥,同时两座桥之间不能交叉.希望可以得到一个尽量多座桥的方案.
问题分析：
首先，这是一个动态规划的问题，即解答有许多中，寻找一个最优的解决方案。
其次，问题抽象，就是怎样将这个问题抽象成一个数学模型进行解决
第一步：就是搞清楚问题是什么？-------就是对号入座A对应于B的序号，这样的解决方案有许多如1,5,4和2,5,4以及1,3
第二步：抽象-------抽象成两个数组S1(1,2,5,4,3), S2(2,1,3,5,4)，然后找S1和S2中相同的数字，且序号必须在数组下标递增，找出最多的对数
(即S1中的1对应了S2中的1，S1中的2对应了S2中的2,虽然S1中的下标是1,2 但是在S2中的下标是2,1没有递增，故而是不行的---更简单的说就是上面图不能交叉)
第三步：找规律--------这是最难的，如何才能从中找到突破口，我们在寻找的过程中发现，联系S1和S2的桥梁是什么？就是组成对的两个数在各自数组中的下标
那我们把这些下标都写出来，只是写一方就可以了从S1到S2的，就设为S3(2,1,4,5,3)---就表示S3[0]=2表示S1数组第一个值对应与S2中的第二个值（这个2就是在S2中的下标）,
从而依次就把S3写出来了，这样找对数最多，而S3表示的是连线时对方的下标，那么是不是只要下标递增就不会交叉了？事实就是这样！！
就是找S3中的最长递增数组，这里就是{2,4,5}或者{1,4,5}
第四步：写代码-------既然突破口找到了，代码就不是问题了
?
代码
?
/***建桥问题**/#include <iostream>#include <cstring>using namespace std;/***建立建桥索引数组*a : 原始数组a*b: 原始数组b*c：建立的索引数组*length ：数组长度*/void build(const int* a, const int* b, int* c, int length){for(int i=0; i<length; i++){for(int j=0; j<length; j++){if(a[i]==b[j]){ c[i]=j+1;//我们建立数组时以1为开始 break;}}}}/***s2：原始数组S2*rt:求出的最大递增子序列*length：数组长度*/void printResult(int* s2, int* rt, int length){int j = 0;for(int i=0; i<length; i++){if(rt[i]==0) break;j = s2[rt[i]-1];cout<<"B"<<j<<"--A"<<j<<" ";}cout<<endl;}/***a : 原始数组*length ：数组长度*sub ：求出的最大递增子序列*/void longestIncreaseSub(int* a, int length, int* sub){int n = length;int *t = new int[n];int *p = new int[n];memset(p,0,sizeof(int));t[0]=1;for(int i=1; i<n; i++){t[i]=1;for(int j=0; j<i; j++){if(a[j]<a[i] && t[j]>t[i]-1){t[i]=t[j]+1;p[i]=j;}}}int m=0,k=0;for (int i=1;i<=n;i++) { if (m<t[i]) { m = t[i]; k = i; } } while(m>=0){ sub[m-1] = a[k]; m--; k = p[k]; }delete[] t;delete[] p;p = NULL;t = NULL;}int main(){int a[] = {1,2,5,4,3};int b[] = {2,1,3,5,4};int length = sizeof(a)/sizeof(int);//索引数组int* c = new int[length];//存储最终结果int* sub = new int[length];memset(sub,0,sizeof(int));//初始化submemset(sub,0,sizeof(int));//初始化subbuild(a,b,c,length);longestIncreaseSub(c,length, sub);printResult(b,sub, length);delete[] c;delete[] sub;c = NULL;sub = NULL; return 0;}?
?b.叠箱子问题
问题描述：
1.一排有许多不同的箱子，长宽高不一样
2.你需要把他叠放的尽量的高.但是箱子的摆放必须满足大的在下面,小的在上面的原则
3.箱子可以任意旋转（这就意味着你要用一个箱子的时候，旋转到合适位置）
问题分析：
具体分析见图：
注1：盒子要比上面的大--准确的说，是Wi>Wj && Di>Dj,单独使用Si>Sj不准确，因为可能很长但很窄，不和题目要求
为了满足要求，我们人为规定，W<=D（输入时确定或者后来处理）,这样就不用担心这个问题了，使用Si>Sj就满足要求。
注2：记住盒子可以旋转，意味着每个盒子可以有三个面可以使用，旋转数量不限。
注3：本体关键是建立模型，列出动态规划的方程
?
代码：
?
/****叠箱子问题*/#include <iostream>#include <vector> #include <cstring>#include <algorithm> using namespace std;//定义一个箱子结构体struct Box{int h;//高int w;//宽int d;//长};//排序比较器bool boxCompare(const Box& a, const Box&b){return a.d*a.w > b.d*b.w;//降序排序}//最高的堆叠高度算法int highestBox(const vector<Box>& b){//初始判断if(b.size()<=0) return 0;//初始化一个vector，长度是原来的三倍，因为每个箱子都有三种翻转方式，每种当成一个新的箱子vector<Box> boxs(b.size()*3);//箱子的处理，使所有的箱子都是w<=d,每个箱子都翻转两次for(int i=0; i<b.size(); i++){//下面是一个箱子的三种翻转情况boxs[i*3+0].h = b[i].h;boxs[i*3+0].w = b[i].w < b[i].d ? b[i].w : b[i].d;boxs[i*3+0].d = b[i].w < b[i].d ? b[i].d : b[i].w;boxs[i*3+1].h = b[i].h;boxs[i*3+1].w = b[i].h < b[i].d ? b[i].h : b[i].d;boxs[i*3+1].d = b[i].h < b[i].d ? b[i].d : b[i].h;boxs[i*3+2].h = b[i].h;boxs[i*3+2].w = b[i].w < b[i].h ? b[i].w : b[i].h;boxs[i*3+2].d = b[i].w < b[i].h ? b[i].h : b[i].w;}//排序(不是boxCompare（）)sort(boxs.begin(), boxs.end(), boxCompare);//最长递增子序列问题vector <int> m(b.size()*3);m[0] = boxs[0].h;for(int i=0; i<boxs.size(); i++){for(int j=0; j<i; j++){if ( (boxs[i].w <= boxs[j].w) && (boxs[i].d <= boxs[j].d) && (m[i] < m[j]+boxs[i].h) )m[i] = m[j]+boxs[i].h;}}int mm = *max_element(m.begin(),m.end());return mm;}int main(){vector<Box> box(3); box[0].h = 2; box[0].w = 3; box[0].d = 4; box[1].h = 2; box[1].w = 3; box[1].d = 1; box[2].h = 5; box[2].w = 3; box[2].d = 4; cout<<highestBox(box)<<endl;return 0;}??