10599 - Robots(II)

题目链接~~>

做题感悟：这题度题意就读了很久，很经典，主要是想到怎样转化。

解题思路：

                如果第  i  个垃圾标号小于第 j 个垃圾，且i 列坐标不大于 j 的列坐标那么就可以由 i 到 j 形成一条路（机器人只向下 ，向右走），这样用dp 一边，跟求最长单调递增序列一样，同时记录到达每个点的方法数 ，还要注意如果在左下角没有垃圾要人为添加一个，到最后输出的时候不输出即可。

代码：

      #include<iostream>
      #include<fstream>
      #include<iomanip>
      #include<ctime>
      #include<fstream>
      #include<sstream>
      #include<stack>
      #include<cstring>
      #include<map>
      #include<vector>
      #include<cstdio>
      #include<algorithm>
      #define INT long long int
      using namespace std ;
      const INT INF = 1000000000 ;
      const INT MY = 59 ;
      const INT MX = 10000 + 10 ;
      INT n ,m ,num ,cse=1 ;
      bool flag ;
      INT g[MX] ,pre[MX] ,dp[MX] ,key[MX] ;
      void input()
      {
      memset(dp ,0 ,sizeof(dp)) ;
      memset(key ,0 ,sizeof(key)) ;
       flag = false ;
       INT x ,y ;
       num = 0 ;
      while(scanf("%lld%lld",&x ,&y) && x+y)
       {
       x-- ; y-- ;
       g[++num] = x*m + y ;
       }
       sort(g+1 ,g+num+1) ;// 切记！给的不一定有序
      if(num && g[num] != n*m-1)
       {
       flag = true ;
       g[++num] = n*m-1 ;
       }
      for(INT i = 0 ;i <= num ;i++)
       pre[i] =  i ;
      }
      void DP()
      {
      for(INT i = 1 ;i <= num ;i++)
       {
       dp[i] = 1 ; key[i] = 1 ;
      for(INT j = 1 ;j < i ;j++)
      if(g[i]%m >= g[j]%m)
       {
      if(dp[i] < dp[j] + 1)
       {
       dp[i] = dp[j] + 1 ;
       key[i] = key[j] ;
       pre[i] = j ;
       }
      else if(dp[i] == dp[j] + 1)
       {
       key[i] +=key[j] ;
       pre[i] = j ;
       }
       }
       }
      cout<<"CASE#"<<cse++<<": " ;
      if(flag)
      cout<<dp[num] - 1<<" "<<key[num] ;
      else   cout<<dp[num]<<" "<<key[num] ;
      }
      void output(INT num) // 递归输出
      {
      if(pre[num] != num)
       {
       output(pre[num]) ;
      cout<<" "<<g[num]+1 ;
       }
      else
      cout<<" "<<g[num]+1 ;
      return ;
      }
      int main()
      {
      while(~scanf("%lld%lld",&n ,&m))
       {
      if(n == -1 && m == -1)  break ;
       input() ;
      if(!num) //
       {
      cout<<"CASE#"<<cse++<<": " ;
      cout<<"0 0"<<endl ;
      continue ;
       }
       DP() ;
      if(pre[num] != num)
       output(pre[num]) ;
      if(!flag)   cout<<" "<<n*m ;
      cout<<endl ;
       }
      return 0 ;
      }
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38562447