work(); return 0; }
【小结】
问题虽然简单，仍然不能放过思考的余地。O(n^3)的算法是可以通过所有测试数据的，但是nlogn的算法里，不但体现了二分法的思想，而且也体现了多次动态规划的思想，这个思想在解决很多问题的时候，都有很大的作用。
【例题4】飞翔1907
Description
鹰最骄傲的就是翱翔，但是鹰们互相都很嫉妒别的鹰比自己飞的快，更嫉妒其他的鹰比自己飞行的有技巧。于是，他们决定举办一场比赛，比赛的地方将在一个迷宫之中。 这些鹰的起始点被设在一个N*M矩阵的左下角map[1，1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角，有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示：
没有障碍，也没有死路。这样设计主要是为了高速飞行的鹰们不要发现死路来不及调整而发生意外。潘帕斯雄鹰冒着减RP的危险从比赛承办方戒备森严的基地中偷来了施工的地图。但是问题也随之而来，他必须在比赛开始之前把地图的每一条路都搞清楚，从中找到一条到达终点最近的路。（哈哈，笨鸟不先飞也要拿冠军）但是此鹰是前无古鹰，后无来鹰的吃菜长大的鹰--菜鸟。他自己没有办法得出最短的路径，于是紧急之下找到了学OI的你，希望找到你的帮助。 Input
首行为n,m(0 < n,m<= 100000),第2行为k（0 < k<= 1000）表示有多少个特殊的边。以
下k行为两个数，i,j表示map[i,j]是可以直接穿越的。 Output
仅一行，1，1-->n,m的最短路径的长度，四舍五入保留到整数即可 Sample Input 3 2 3 1 1 3 2 1 2
Sample Output 383 【试题分析】
【例题５】buy low，buy lower逢低吸纳
“低价购买”这条建议是在奶牛股票市场取得成功的一条规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议：“低价购买；再低价购买”。每次你购买一支股票，你必须用低于你上次购买股票的价格购买它。买的次数越多越好！你的目标是在遵循以上建议的前提下，求你最多能够购买股票的次数。你将会得到一段时间内一支股票每天的出售价（2^16范围内的正整数），你可以选择在那些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一程序计算最大购买次数。 这里是某支股票的价格清单： 日期 1 2 3 4 5 6 7 8 9 10 11 12
价格 68 69 54 64 68 64 70 67 78 62 98 87
最优秀的投资者可以购买最多4次股票，可行方案中的一种是： 日期 2 5 6 10 价格 69 68 64 62 Input
第一行：n（1 <= n <= 5000），股票发行天数；第二行：n个数，是每天的股票价格。 Output
输出文件仅一行包含两个数：最大购买次数和拥有最大购买次数的方案数（小于等于2^16）当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候），这2种方案被认为是相同的。
【试题分析】
问题的第一部分是要求得到输入数据串中的一个最长下降序列的长度，可使用动态规划的方法。具体做法是从序列的最后一个元素开始，依次求出以第i个元素为第一个元素时的最长下降序列的长度len[i]，显然len[n]=1，len[i]=max(len[j]+1)，其中i 第二部分比较有难度。由于它紧接着第一问，所以一般说来应该充分利用第一个问题的结论，对于任意一个最长下降序列，设它的第一个元素的下标为i1，第二个元素的下标为i2，其余元素的下标以此类推，则显然有len[i1]=maxlen，len[i2]=maxlen-1，…，现在要求所有不同的最长下降序列的总数，则只要求按照数组len的值从小到大对整个序列从后向前递推即可。以序列a=(5,3,1,4,2)为例。Len[1]=3，len[2]=2，len[3]=1，len[4]=2，len[5]=1，用t[i]记录以第i个元素为头一个元素到序列结束为止的最长下降序列的不同方案总数，若len[i]=1，则t[i]=1，本例中由len[3]=1，len[5]=1可知t[3]=1，t[5]=1，再由len[5]=1，len[4]=2且a[4]=4>a[5]=2可得t[4]=1，由len[5]=1,len[2]=2且a[2]=3>a[5]=2和len[3]=1,len[2]=2且a[2]=3>a[3]=1可得t[2]=t[5]+t[3]=2，对应{a[2],a[3]}和{a[2],a[5]}两个不同的以a2起头的最长下降序列，最终由len[4]=2,len[1]=3且a[1]=5>a[4]=4和len[2]=2,len[1]=3且a[1]=5>a[2]=3可得t[1]=t[4]+t[2]=1+2=3，所以本例中最长下降序列总数为3，分别为{5，4，2}，{5，3，2}和{5，3，1}。对于有相同元素的序列来说，如序列a=(5，4，1，4，2)，其中有两个相同的元素4，前面的推导过程不变，最后一步推导受两个相同元素的影响，不能简单相加，由于a2=a4=4，对于所有的以a4起头的最长下降序列，只要将a4改为a2即可得到同样长度的下降序列，所以t[4]中的统计的序列在t[2]中也统计在内了，当序列中有相同元素时，为避免重复计数，从后向前递推时当后面的元素遇到前面的相同元素时则不再向前推。程序中为了方便处理，在整个序列前设置了一个标识元素a[0]=maxlongint,将len[0]置为maxlen+1。 #include int date[5005]; int st[5005];//长度 int sum[5005];//方案 int res1 = 0, res2 = 0; int main() { scanf(\ int i, j; for(i=1; i<=n; i++) scanf(\ for(i=n; i>=1; i--) { st[i] = sum[i] = 1; for(j=i+1; j<=n; j++) { if(date[j] < date[i]) { if(st[j] >= st[i]) { st[i] = st[j]+1; sum[i] = sum[j]; } else if(st[j] == st[i]-1) sum[i] += sum[j]; } else if(date[j] == date[i]) { sum[j] = 0; } } } for(i=1; i<=n; i++) { if(st[i] > res1) { res1 = st[i]; res2 = sum[i]; } else if(st[i] == res1) res2 += sum[i]; } printf(\ return 0; } 下面的程序采用了hash判重来处理相同的数 #include int a[5001],f[5001],p[5001]; bool hash[30001]; int main() { int n,i,j; cin>>n; memset(p,0,sizeof(p)); for(i=1;i<=n;i++) {scanf(\ p[n]=1; for(i=n-1;i>=1;i--) { for(j=i+1;j<=n;j++) if(a[j]f[i]) f[i]=f[j]+1; if(f[i]==1) {p[i]=1;continue;} memset(hash,0,sizeof(hash)); for(j=i+1;j<=n;j++) if(a[j] int max=1,sum=0; for(i=2;i<=n;i++) if(f[i]>f[max]) max=i; cout< memset(hash,0,sizeof(hash)); for(i=1;i<=n;i++) if(f[i]==f[max]&&hash[a[i]]==0) {sum+=p[i];hash[a[i]]=true;} cout< 附：最长上升子序列(LIS)的O(nlogn)算法 思想：以a[i]结尾的长度为x上升子序列，若a[i]越小的话则后面长度增长的可能性更大。当前面有多个同等长度的序列时，我们只需存储尾部元素最小的即可。这样，我们存储的所有这样的尾部元素序列就变为一个上升序列，序列的长度就为最终所求。 开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈（加长了一位）；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它(换了一个小的)。 最长序列长度即为栈的大小top。 这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x] 替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。 举例：原序列为1，5，8，3，6，7 栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。 #include { int i, j, n, top, temp; int stack[1001]; cin >> n; top = 0; /* 第一个元素可能为0 */ stack[0] = -1; for (i = 0; i < n; i++) { cin >> temp; /* 比栈顶元素大数就入栈 */ if (temp > stack[top]) { stack[++top] = temp; } else { int low = 1, high = top; int mid; /* 二分检索栈中比temp大的第一个数 */ while(low <= high) { mid = (low + high) / 2; if (temp > stack[mid]) { low = mid + 1; } else { high = mid - 1; } } /* 用temp替换 */ stack[low] = temp; } } /* 最长序列数就是栈的大小 */ cout << top << endl; return 0; } 递推类型DP 【例题1】：数字三角形1077 Description 如下所示一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 ●每一步可沿左斜线向下或右斜线向下走； ●1＜三角形行数≤100； ●三角形中的数字为整数0，1，…99； Input：输入第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三 角形． Output：输出仅有一行包含一个整数（表示要求的最大总和） Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output：30 【试题分析】 （1）从底层开始，本身数值即为最大数。 （2）倒数第二层的计算，将决定于底层。 （3）最后路径为13---8----26---8-24 1、阶段和状态：本题是一个非常典型的递推类型的数字三角形问题。由于每层是相互独立，不互相影响的，所以此题可以以每一层为阶段用动态规划求解。 a[i][j]：表示各点的数字值; f[i][j]：表示从第n层到(i,j)这点，该路径所经过的数字的最大总和； 阶段：层数i；状态：列数j 1、 状态转移方程： 初始值：f[n][i]=a[n][i];(1<=i<=n) 状态转移方程：f[i][j]=max{f[i+1][j]，f[i+1][j+1]}+a[i][j]; (1<=i<=n-1;1<=j<=i) Answer=f[1][1] 3、核心子程序： int main () { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++)cin>>a[i][j]; //读入数据 for(i=1;i<=n;i++)f[n][i]=a[n][i]; //初始化 for (i=n-1;i>=1;i--) //阶段行数 for (j=1;j<=i;j++) //状态列数 f[i][j]=maxx(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);//决策 cout<