学步园

本题目一开始直接不敢用把所有点排序求LIS和LIS的个数，点最多有10000会超时的，但交上去不到0.1秒；可能后台数据点最多也就1000个左右；

求LIS不用详解了，很水的两重循环求得，在此过程中保留以每个点为终点的最大长度串的个数；还要在记录一个前驱即可打印路径；

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 10005;

int d[maxn],rec[maxn],cnt[maxn],n,m,maze[105][105],a[maxn];
void print_ans(int j){
   if(rec[j] !=-1)
     print_ans(rec[j]);
   printf(" %d",a[j]+1);
}
int main()
{
    int kase=1;
    while(scanf("%d %d",&n,&m)==2){
         if(n==-1) break;
         int x,y;
         memset(maze,0,sizeof(maze));
         while(scanf("%d %d",&x,&y)&&x&&y){
            maze[x][y]=1;
         }
         int kk=0;
         for(int i=1;i<=n;i++)
           for(int j=1;j<=m;j++){
             if(maze[i][j]){
                a[kk++]=(i-1)*m+j-1;
             }
         }
         int flag =false;
         if(a[kk-1]!=n*m-1){
                a[kk++] = n*m-1;
                flag = true;
         }
         for(int i=0;i<kk;i++) d[i] = 1;

         for(int i=0;i<kk;i++){
            cnt[i] = 1;  rec[i] = -1;
            for(int j=0;j<i;j++){
                if(a[j]%m <= a[i]%m){
                    if(d[j]+1>d[i]){
                        d[i]=d[j]+1;
                        cnt[i] = cnt[j];
                        rec[i] = j;
                    }
                    else if(d[j]+1==d[i]){
                        cnt[i] += cnt[j];
                    }
                }
            }
         }
         if(flag) d[kk-1]--;
         printf("CASE#%d: %d %d",kase++,d[kk-1],cnt[kk-1]);
         if(flag)
            print_ans(rec[kk-1]);
         else print_ans(kk-1);
         printf("\n");
    }
    return 0;
}