經典的最長不下降子序列問題，O(n^2)【還存在基于二分查找的O(nlogn)算法】

方程：if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)

可能是今天狀態不好，一直在糾纏細節.需要注意的是，子序列長度的最大值不一定在f[n]中.

 1#include<iostream>
 2using namespace std;
 3int a[5001], b[5001];
 4int max(int x, int y) {return (x > y) ? x : y;}
 5int main()
 6{
 7    int i, j, n, ans;
 8    cin >> n;
 9    for (i = 1; i <= n; i++) {cin >> a[i]; b[i] = 1;}
10    for (i = 2; i <= n; i++)
11    {
12        for (j = 1; j < i; j++)
13            if (a[j] <= a[i] && b[j]+1 > b[i])
14                b[i] = b[j]+1;
15    }
16    for (i = 1; i <= n; i++) 
17        if (ans < b[i]) ans = b[i];
18    cout << ans << endl;
19}
20

馬上要走了，高中還是麻煩很多，進度讓人糾結.

報名的問題已經順利解決，特別感謝新班主任xm老師在12h內聯系好了本部的教練，以及教練dh老師.

上機時間初步定在16:30之后，等待教練通知.

——————————-古事·故事——————————-

NOIP 2009高級出了一等，當年普及兩一等的lj神牛，第一年三等，第二年一等.

很神奇的掛靠中山紀念參賽.

不知如何聯系.

很多事情總是莫名奇妙的，比如OI，聽來的故事可以寫成長篇.

比如lccz，兩位令人尊敬的學長，lwq和jec，一個復賽二等，一個初賽全市第三.

• 一個在龍高，一個在深中.
• 前者高二二等，高三三等；后者高一一等.

再比如，lj 和dy，同樣是兩位令人尊敬的學長.

• 前者是初中深圳市實力最強的，來自深中初中部，初二一等300+，初三一等290.之后莫名其妙的去了高級，代表紀中參賽，高一三等210，高二一等210.
• 后者初三沒進復賽，去了深中，高一二等250，高二一等265，今年又拿了NOI銅牌，是深圳歷史上第一個NOI獎牌得主.

環境雖然不是決定性的，但對人的限制仍然不可忽視.

保證基本環境，剩下的，事在人為.

—————————–進度——————————-

• 《背包九講》看了一半，dd_engi的語言果然不易理解，加深了對01背包、完全背包、多重背包的認識.需要學習某些特殊的情況.需要做題.
• 刷了1998和1999原題，明天打程序，1999最后一題不會.(DP+搜索)
• 重新用了龍初的vijos，重建一個提高題庫，這應該能節約一些時間，畢竟每天可能的上機時間也就1-1.5h.
• 現在效率太低了.