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