uva 10599 Robots(II)

标题:n*mの行列をあげて、k座標(0,0で終わる)をあげて、上に物があることを示して、それからロボットが右へ行くことと下へ行くことしかできなくて、起点は左上の角で、終点は右下の角で、あなたに聞いて、機械は起点から終点まで最大で何個の物を取ることができます.前に出力するパスのうちの1つ(アイテムの座標で表される)を示し、非降下サブシーケンスがどれだけあるかを抽象化することができます.
私の考えは:最長の上昇サブシーケンスを求めるとき、行列で表して、私たちが1つの物品を入れるとき、私たちはまず現在すでに得た最も長い上昇サブシーケンスから探して(つまりimax層)、もし現在の層が見つからないならば、私たちはその上の層を探して......もし1つを見つけたら、私たちはすぐに飛び出します.同時に見つけたこの品物を対応する層に入れます.これで最も長い上昇サブシーケンスを見つけることができますが、パス数をどのように記録しますか?各レイヤの各要素には、このレイヤに到達する要素のパス数を記録する値があります.では、どのようにして要素のパス数を得ることができますか?この層のある層を押し出すことができるすべての要素が条件に合致する経路を合わせると、この要素に到達する経路数になります.
どうしてTでしないの?まず,求め経路数と最長上昇サブシーケンスを統合した.
そして、プッシュするときは、だからの要素と判断しないで、ある層を見つけてすぐに飛び出します.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
const int N=10055;
struct BAG
{
    int x,y,p;
}bag[N];
struct node
{
    int x,y,ind;
    LL rout;
    node(){x=0;y=0;ind=0;rout=0;}
    node(int a,int b,int c,LL d){x=a;y=b;ind=c;rout=d;}
};
vector<node> layer[N];
int n,m;
void init();
void print(int);
bool cmp(const BAG &a,const BAG &b)
{
    return a.x!=b.x?a.x<b.x:a.y<b.y;
}
int main()
{
    //freopen("10599","r",stdin);
    int t_cnt=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==-1&&m==-1) break;
        init();
        int x,y,t=0,imax=0;
        while(1)
        {
            scanf("%d%d",&x,&y);
            if(x==0&&y==0) break;
            bag[t].x=x;bag[t].y=y;bag[t++].p=-1;
        }
        printf("CASE#%d: ",++t_cnt);
        if(t==0) {puts("0 0");continue;}
        sort(bag,bag+t,cmp);//                      。
        bag[0].p=-1;//    。
        layer[0].push_back(node(bag[0].x,bag[0].y,0,(LL)1));
        for(int i=1;i<t;i++)
        {
            LL times=0;//         。
            bool flag=0;//          。
            for(int j=imax;j>=0;j--)
            {
                int pos,len=layer[j].size();
                for(int k=0;k<len;k++)
                {
                    if(layer[j][k].x<=bag[i].x&&layer[j][k].y<=bag[i].y)//      
                    {
                        flag=1;
                        times+=layer[j][k].rout;
                        pos=layer[j][k].ind;//              ，  pos       。 ind         
                    }
                }
                if(flag)//     ，            。
                {
                    layer[j+1].push_back(node(bag[i].x,bag[i].y,i,times));
                    bag[i].p=pos;
                    imax=max(imax,j+1);
                    break;
                }
            }
            if(!flag)
            {
                layer[0].push_back(node(bag[i].x,bag[i].y,i,(LL)1));
                bag[i].p=-1;
            }
        }
        LL times=0;
        for(int i=layer[imax].size()-1;i>=0;i--)
        {
            times+=layer[imax][i].rout;
        }
        printf("%d %lld",imax+1,times);
        print(layer[imax][0].ind);
        puts("");
    }
    return 0;
}
void init()
{
    for(int i=0;i<N;i++) layer[i].clear();
    memset(bag,0,sizeof(bag));
}
void print(int pos)
{
    if(pos==-1) return;
    else
    {
        print(bag[pos].p);
        printf(" %d",m*(bag[pos].x-1)+bag[pos].y);
    }
}