問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1887http://acm.pku.edu.cn/JudgeOnline/problem?id=2533思路:
典型而簡單的動態(tài)規(guī)劃，類似于最大子段和的思想:
f[i]表示以num[i]結(jié)尾的最長下降(上升)子序列，那么:
f[i] = max (f[j]+1, if num[j]>num[i] && 0<=j<i)
原本挺簡單的代碼，一會就寫完了，結(jié)果卻因為一個臨時變量的初始化錯誤而WA了好多次，要細(xì)心...
上述是O(n^2)的算法，另外還有O(nlgn)的算法，下回嘗試。
代碼(pku 1887):
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 32767
5 int num[MAX_LEN];
6 int max[MAX_LEN];
7 int len;
8
9 /*
10 * f[i] represent the longest descent sequence ended with num[i], so:
11 * f[i] = max ( f[j]+1, if num[j]>num[i], 0<=j<i)
12 */
13 int
14 dp()
15 {
16 int i, j, t, rt;
17 max[0] = rt = 1;
18 for(i=1; i<len; i++) {
19 t = 1; /* WA twice here, for t=-1 */
20 for(j=0; j<i; j++) {
21 if(num[j] > num[i])
22 t = max[j]+1>t ? max[j]+1 : t;
23 }
24 max[i] = t;
25 rt = max[i]>rt ? max[i] : rt;
26 }
27 return rt;
28 }
29
30 int
31 main(int argc, char **argv)
32 {
33 int i, tmp, cnt = 0;
34 while(scanf("%d", &tmp)!=EOF && tmp!=-1) {
35 num[0] = tmp;
36 len = 1;
37 while(scanf("%d", num+len)!=EOF && num[len]!=-1)
38 ++len;
39 printf("Test #%d:\n maximum possible interceptions: %d\n\n", ++cnt, dp());
40 }
41 }