UVA10131 Is Bigger Smarter? 简单动态规划 - c++编程基础

UVA确实挺坑，交个题能卡半年，全是JE，不是中国的白天是美国的晚上吗？服务器有那么爆满吗？

题意：一群大象，每头大象有两个属性1：体重 2：IQ，现在从这些大象里挑出大象来排队，队伍有两个要求，每一头大象的体重必须比前一头大，IQ必须比前一头小，求此队伍的最长长度，并列出队伍中大象的序号，序号按照输入给的顺序，序号从1开始

如果我们只看体重或者 IQ会发现就是一个最长子序列问题，只看体重是一个最长上升子序列，只看IQ是一个最长下降子序列，那么其实我们可以先满足其中一个条件再这个基础上进行最长子序列求解，如果我们先把大象仅按体重来排序，那么我们只要求满足IQ的最长下降子序列长度，如果我们先把大象仅按IQ来排序，那么我们只要求满足体重的最长上升子序列即可，所以这道题目先进行排序，就能转化成一道简单的 DP问题了，直接用最土的n^2复杂度都能过，当然题目要求的输出路径还是比较烦得，可以开一个数组记录路径编号，等 dp过程完了以后呢，就可以从最后一个编号递归回去，进行递归输出路径即可，

顺便推荐一个博客，是最长子序列问题的题集合，几道水题，做做可以打好基础：http://blog.csdn.net/wangkechuang/article/details/7949151

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) struct Node { int w,s; int id; }node[10000 + 5]; int dp[10000 + 5]; int mark[10000 + 5]; int ans; void clear() { memset(dp,0,sizeof(dp)); memset(node,0,sizeof(node)); memset(mark,0,sizeof(mark)); } bool cmp(Node x,Node y) { return x.w < y.w; } void Printf(int x) { if(ans--) { Printf(mark[x]); printf("%d\n",node[x].id); } } int main() { int n = 1; while(scanf("%d %d",&node[n].w,&node[n].s) != EOF) { node[n].id = n; n++; } n--; sort(node + 1,node + n,cmp); for(int i=1;i<=n;i++) { dp[i] = 1; mark[i] = i; } ans = -1; int cnt; for(int i=2;i<=n;i++) { for(int j=1;j
                    
                      node[j].w && node[i].s < node[j].s) { if(dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; mark[i] = j; } } if(ans < dp[i]) { ans = dp[i]; cnt = i; } } } printf("%d\n",ans); Printf(cnt); return EXIT_SUCCESS; }