题目大意：给一个建筑的序列，建筑用高度和宽度描述，找出按高度的LIS和LDS，最长XX子序列的长度按照序列中建筑的宽度和进行计算。
其实就是带权的最长XX子序列问题，原来是按个数计算，每个数权都是1，现在有不同的权重。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 #define MAXN 100000 5 6 int h[MAXN], w[MAXN], lis[MAXN], lds[MAXN]; 7 8 int main() 9 { 10 #ifdef LOCAL 11 freopen("in", "r", stdin); 12 #endif 13 int T; 14 scanf("%d", &T); 15 for (int kase = 1; kase <= T; kase++) 16 { 17 int n; 18 scanf("%d", &n); 19 for (int i = 0; i < n; i++) 20 scanf("%d", &h[i]); 21 for (int i = 0; i < n; i++) 22 scanf("%d", &w[i]); 23 for (int i = 0; i < n; i++) 24 { 25 lis[i] = lds[i] = w[i]; 26 for (int j = 0; j < i; j++) 27 { 28 if (h[i] > h[j]) lis[i] = max(lis[i], lis[j]+w[i]); 29 if (h[i] < h[j]) lds[i] = max(lds[i], lds[j]+w[i]); 30 } 31 } 32 int a = 0, b = 0; 33 for (int i = 0; i < n; i++) 34 { 35 a = max(a, lis[i]); 36 b = max(b, lds[i]); 37 } 38 if (a >= b) printf("Case %d. Increasing (%d). Decreasing (%d). ", kase, a, b); 39 else printf("Case %d. Decreasing (%d). Increasing (%d). ", kase, b, a); 40 } 41 return 0; 42 }