【算法分析】
首先考虑第一问，即序列中的最长不上升子序列。

令 g 为以 i 结尾的最长不上升子序列的值，那么可以枚举 g 
1
​
 ~ gi−1，若 a 
j
​
 ≤a 
i
​
 ，则 g 
i
​
 =max(g 
i
​
 ,g 
j+1
​
 )，否则 g 
i
​
 =max(g 
i
​
 ,g 
j
​
 )。这么做显然是 O(n 
2
 ) 的，需要进行优化。

若 a 
i
​
  小于等于 g 的最后一个元素，那么显然将 a 放至 g 的末尾。否则，将 a 
i
​
  替换掉 g 中第一个小于等于 a 
i
​
  的值。为什么这样做呢?假设 g 
j
​
  是 g 中第一个小于等于 a 
i
​
  的值，那么 g 
j−1
​
  一定大于 a 
i
​
 ，若替换掉这一个，则肯定不划算(因为 g 
j−1
​
  会变小，但是答案没有变)，而替换掉 g 
j
​
 ，则答案不变的同时 g 
j
​
  会变大，更加划算。

那么答案显然就是 g 数组的长度，可以用二分来查找「g中第一个小于等于a 
i
​
  的值」，复杂度(nlog 
2
​
 n)。

第二问见注释。

【参考代码】
#include <iostream>
using namespace std;

const int N = 5e5 + 10;
int a[N], x, n, dp[N], maxn;
int g[N], cnt;

int main() {
    while (cin >> x) a[++n] = x;
    g[0] = 5e4; 
    for (int i = 1; i <= n; i++) {   //构造最长不上升子序列 
        if (a[i] <= g[cnt]) g[++cnt] = a[i]; //ai小于 g 中最后一个元素，将 ai 放末尾 
        else {  //ai大于 g 中最后一个元素，找到 g 中第一个小于等于 ai 的值元素，交换 
            int l = 1, r = cnt;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g[mid] < a[i]) r = mid;
                else l = mid + 1;
            }
            g[l] = a[i];
        }
    }
    cout << cnt << endl;   // 答案为 最长不上升子序列 的长度 
    cnt = 0;
    g[0] = -5e4;
    for (int i = 1; i <= n; i++) {   //gi表示第 i 个系统拦截的最低的导弹是什么,是一个上升子序列
        if (a[i] > g[cnt]) g[++cnt] = a[i]; //ai 大于 g 中最后一个元素，需要新的导弹拦截系统 
        else { //ai 小于等于 g 中最后一个元素， 找到 g 中第一个大于等于 ai 的元素，交换
            int l = 1, r = cnt;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            g[l] = a[i];
        }
    }
    cout << cnt << endl;   
    return 0;
}

【算法分析】
状态数组 vis 对障碍物进行标记，遇到障碍物则方案数为 0。
递推式: f[i][j] = (f[i - 1][j] + f[i][j - 1]) % 100003;

【参考代码】
#include <iostream>
using namespace std;

const int N = 1e3 + 10;
int f[N][N];
bool vis[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        vis[x][y] = true; //标记 
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){ 
            if(!vis[i][j] ) f[i][j] = (f[i - 1][j] + f[i][j - 1]) % 100003;
            if(i == 1 && j == 1) f[i][j] = 1;
        }
    }
    cout << f[n][n];
    return 0;
}

【算法分析】
建六个栈，代表每一根弦上的音调。

对于每次输入，如果栈顶比它小，就进栈，否则一直弹栈直到栈顶的数小于等于它。每次弹栈或进栈都要累计答案，最后输出即可。

【参考代码】
#include <iostream>
#include <stack>
using namespace std;

stack<int> st[7]; //六根弦的音调 

int main() {
    int n, p, ans = 0;
    cin >> n >> p;
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        while(!st[x].empty() && st[x].top() > y){
            ans++; //栈顶比当前的大，出栈
            st[x].pop(); 
        }
        if(!st[x].empty()){ //栈里还有数 
            if(st[x].top() == y) continue;
            ans++;
            st[x].push(y); 
        } else {  //栈空直接进栈 
            ans++;
            st[x].push(y);
        }
    }
    cout << ans; 
    return 0;
}

【算法分析】
对一条鱼来说，它的最优策略是:从小到大地吃掉其它所有的鱼。
注意到，由这个策略，可以发现鱼的存活与否满足单调性，即，如果一条鱼能活下来，比它大的鱼一定都能活下来，如果一条鱼活不下来，比它小的一定都活不下来。

注意边界情况:如果所有鱼的大小相同，则最大的鱼也没法吃掉其它所有的鱼，因此二分需要考虑所有鱼都无法活到最后的情况。

【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5e5 + 10;

struct node{
    int w; //质量
    int id; //编号 
}a[N];
int n;
int vis[N];

bool cmp(node x, node y){
    return x.w < y.w;
}

bool check(int x){ // 该鱼是否可以吃完其它所以的鱼 
    long long t = a[x].w;
    for(int i = 1; i <= n; i++){
        if(i == x) continue;
        if(t <= a[i].w) return false;
        t += a[i].w;
    }
    return true;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].w;
        a[i].id = i;
    }
    sort(a + 1,a + n + 1,cmp);
    int l = 1, r = n, ans = n + 1; //当鱼的重量全部相等时，最大的鱼也不能吃掉所有的鱼，ans = n + 1 
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;  
        }
    }
    for(int i = 1; i <= n; i++){
        if(i < ans) vis[a[i].id] = false;
        else vis[a[i].id] = true;
    } 
    for(int i = 1; i <= n; i++){
        if(vis[i]) cout << 'T';
        else cout << 'N';
    }
    return 0;
}