做题感悟：这题度题意就读了很久，很经典，主要是想到怎样转化。
解题思路：
如果第 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 ;
}