题意：

       输入一些大象的的重量和智商，找出满足：按重量严格递增，智商严格递减（严格递减的意思就是只能小于，不能等于）的最长的序列。

解法：

      参照小白书上的方法，将问题转换为求DAG上的最长路径问题（此题显然不存在自环、闭环以及重复边，因此可以转换为DAG问题）。

      DAG使用邻接矩阵G存放，G[i][j] = true表示第i头大象重量大于第j头大象，且第i头大象智商小于第j头大象。

     注意此题的最长路径是不固定起点和终点的，这里用的是记忆化DP（dijkstra等算法当然也能行得通）。使用DP[i]表示从i出发的最长路径，状态转移方程简单来讲就是：

从i出发的最长路径 = 所有i的邻居中最长路径 + 1。 

即 DP[i] = max(DP[j] + 1), G[i][j] == true。

#include <iostream> #include <algorithm> #include <cstring> using namespace std; bool G[1001][1001]; int DP[10010], n; int dp(int i) { if (DP[i] > 0) return DP[i]; int k = 1; for (int j = 1; j <= n; j++) if(G[i][j]) k = max(k,1 + dp(j)); return DP[i] = k; } void printg(int i) { cout << i << endl; for (int j = 1; j <= n; j++) if (G[i][j]&&DP[j] + 1 == DP[i]) { printg(j); break; } } int main() { int a[1001][2], mi = 0; memset(G, 0, sizeof(G)); memset(DP, 0, sizeof(DP)); for (n = 1; cin >> a[n][0] >> a[n][1]; n++); for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) { G[i][j] = (a[i][0]<a[j][0] && a[i][1]>a[j][1]) ? true : false; G[j][i] = (a[j][0]<a[i][0] && a[j][1]>a[i][1]) ? true : false; } for (int i = 1; i <= n; i++) if (dp(i) > DP[mi]) mi = i; cout << DP[mi] << endl; printg(mi); return 0; }