开始觉得这道题果断是用LCS解的，因为只要把大象的编号分别按照体重从小到大排序获得序列一，然后再将原始编号按照智商从大到小排序获得序列二。然后两个序列求最长子序列即可。但是后来发现这样做有问题，题目中要求所得子序列的体重或是智商都是严格单调的。解决方法其实也简单，只要在编号匹配的情况下，，智商和体重都和前一个已经匹配的大象不一样就可以了。不过…..这种方法始终wrong answer。我想可能是因为智商或者体重都存在重复，因此在最初排序的时候结果是不唯一的。例如在根据智商排序的编号序列中，智商相同的编号其实是可以随意交换位置的…..
后来没有办法了，只能用DAG求解。
#include <iostream>#include <cstdio>#include <vector>#include <algorithm>#include <cstring>#define MAX 1000+5using namespace std;int G[MAX][MAX],d[MAX];vector<int> W,S,R;int n=1;int dp(int i){int& ans=d[i];if(ans>0) return ans;ans=1;for(int j=0;j<n;j++) if(G[j][i]) dp(j)+1>ans?ans=dp(j)+1:ans=ans;return ans;}void print(int i){cout<<i+1<<endl;for(int j=0;j<n;j++) if(G[j][i]&&d[i]==d[j]+1){//找到上一个节点print(j);break;}return ;}int main(){int w,s; while(cin>>w>>s){W.push_back(w);S.push_back(s);n++; } n–;memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); for(int i=0;i<n;i++) for(int j=0;j<n;j++)if(W[i]>W[j]&&S[i]<S[j]) G[i][j]=1;//反向操作，以便正向打印for(int i=0;i<n;i++) dp(i);int pos=0,Max=d[0]; for(int i=0;i<n;i++) if(d[i]>d[pos]) {pos=i,Max=d[i];}//取最大值 cout<<Max<<endl;print(pos);//打印输出 return 0;}
没有什么可凭仗，只有他的好身体，没有地方可去，
