被這個(gè)問(wèn)題困住了，就像憋了一泡屎，但是便秘了，不往下說(shuō)了，你懂的。

　　在網(wǎng)上查了各種資料，各種文章，其實(shí)大家說(shuō)的都差不多，無(wú)非是枚舉、求該序列和它的排序后的序列的最大公共子序列、動(dòng)態(tài)規(guī)劃、基于〈二分法和統(tǒng)計(jì)研究〉論文。最基本最正常路子應(yīng)該是動(dòng)態(tài)規(guī)劃，很多人會(huì)給出一個(gè)公式，然后給出一段代碼，我看了很多，最終只看懂了一個(gè)。描述如下：

　　比如：另d[i]表示數(shù)列1到i，?以i結(jié)尾的最大長(zhǎng)度值，?而令d[i] = max{ d[j]+1}?（1<=j<=i-1 && a[j] > a[i]）也就是說(shuō)，對(duì)于每個(gè)可以接上的值，?都有a[j] > a[i]（遞減），?看誰(shuí)能接的長(zhǎng),?自然就是最優(yōu)解了。如果沒(méi)有可接的，?就說(shuō)明對(duì)于a[i]前邊的沒(méi)一個(gè)值，?都有a[j]>a[i]，?也就是說(shuō)a[i]是迄今位置最大的數(shù)了，?那么有d[i] = 1；

　　單看這個(gè)，想寫(xiě)出程序來(lái)也很難，所以，最好還是直接看程序。

　　對(duì)于poj上的1952題，難點(diǎn)其實(shí)是在計(jì)數(shù)上，m[i]用來(lái)存放計(jì)數(shù)，何時(shí)初始化計(jì)數(shù)？計(jì)數(shù)如何增加？如何防止重復(fù)？這是幾個(gè)要考慮的問(wèn)題，答案都在代碼中了。

輸入用例：

12
68 69 54 64 68 64 70 67 78 62 98 87

輸出用例：

4 2 //最長(zhǎng)是4；有2個(gè)長(zhǎng)度為4的子序列

源程序：

1 #include <stdio.h> 2 int array[5000+1]; 3 int d[5000+1]; 4 int m[5000+1]; 5 int lds(int n) 6 { 7 int max; 8 int i, j; 9 for(i=n-1; i>=0; --i) 10 { 11 for(j=i+1; j<n; ++j) 12 { 13 if(array[i] > array[j]) 14 { 15 if(d[i] < d[j]+1) 16 { 17 d[i] = d[j]+1; 18 m[i] = m[j]; 19 } 20 else if(d[i] == d[j]+1) 21 { 22 m[i] += m[j]; 23 } 24 } 25 else if(array[i] == array[j]) 26 { 27 if(d[i] == 1) 28 { 29 m[i] = 0; 30 } 31 break;//防止重復(fù) 32 } 33 } 34 } 35 for(i=0, max=0; i<n; ++i) 36 { 37 if(max < d[i]) 38 { 39 max = d[i]; 40 } 41 } 42 int maxm; 43 for(i=0, maxm=0; i<n; ++i) 44 { 45 if(d[i] == max) 46 { 47 maxm += m[i]; 48 } 49 } 50 printf("%d %d\n", max, maxm); 51 return 0; 52 } 53 int main() 54 { 55 int i=0; 56 int nLastNum = -1; 57 int nArrayLen; 58 scanf("%d", &nArrayLen); 59 i=0; 60 while(i < nArrayLen) 61 { 62 scanf("%d", &array[i]); 63 m[i] = 1; 64 d[i] = 1; 65 ++i; 66 } 67 while(i<5001) 68 { 69 m[i] = 1; 70 d[i] = 1; 71 ++i; 72 } 73 lds(nArrayLen); 74 return 0; 75 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/favourmeng/archive/2012/08/28/2660200.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的最长单调子序列及计数（poj1952）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。