本文主要是介绍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 ;}elsecout<<" "<<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 ;
}
这篇关于10599 - Robots(II)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
