posts - 99, comments - 8, trackbacks - 0

//動態(tài)規(guī)劃題目最重要的一點(diǎn)是如何將問題分解得到子問題，并且將子問題解決
//本題以下標(biāo)為狀態(tài)量，找到以該下標(biāo)位置 i 為終點(diǎn)時的最長子列：如果 i 位置的值 > i - 1位置的值，則長度加 1 ，
//所以利用判斷大小來遞歸，出口是：下表為 0 時，長度為 1
//利用 nMaxLen【i】記錄長度避免了重復(fù)計(jì)算

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int main ()

{

int n;

int b[1000];

int nMaxLen[1000];

while (scanf ("%d", &n) != EOF && 1 <= n && n <= 1000)

{

memset (nMaxLen, 0 ,sizeof(nMaxLen));

//將輸入的數(shù)值存入數(shù)組 b 中

for (int i = 0; i < n; i ++)

{

scanf ("%d", &b[i]);

}

//找到每一個狀態(tài)下標(biāo) i 對應(yīng)的最大子列長度，并將其存入數(shù)組nMaxLen[]中

nMaxLen[0] = 1;

for (int i = 1; i < n; i ++)

{

int temp = 0;

for (int j = 0; j < i ; j ++)

{

if ( b[i] > b[j])

{

if (temp < nMaxLen[j]) //只有當(dāng)當(dāng)前的長度 < 之前一位數(shù)的序列長時才可以賦值，最后起到 temp + 1 的作用
// 為什么:最大序列可能出現(xiàn)在 j 之后如： 7 9 10 6 11

temp = nMaxLen[j];

}

nMaxLen[i] = temp + 1;

}

//遍歷數(shù)組nMaxLen從中讀出最大值，即：在該位置時取得最大的子序列

int max = -1;

for (int i = 0; i < n; i ++)

{

if (nMaxLen[i] > max)

max = nMaxLen[i];

}

printf ("%d\n", max);

}

//system ("pause");

return 0;

}

posted on 2010-08-14 15:38 雪黛依夢閱讀(204) 評論(0) 編輯收藏引用所屬分類: 動態(tài)規(guī)劃

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: hdu 1160 簡單題 hdu 1466 DP 直線的可能交點(diǎn)數(shù)目 hdu 1087 DP grids 2757 求最大子例長度 hdu 2050 折線分割平面

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理