首页 > 代码库 > POJ2111 Millenium Leapcow

POJ2111 Millenium Leapcow

题解:

类似滑雪,只不过增加了最小路径输出

路径如何输出?

以递归形式保存在路径中,最后保存最终解的开始点,然后递归输出

如何最小路径?贪心,使得每个点能走的最长路径最长,在相同的情况下记录最小前驱

代码:

#include<iostream>#include<vector>#include<cstdio>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=200100;const int mod=1e9+7;const int INF=1e9;int M[370][370],dp[370][370];P path[370][370];vector<P> v;int n;int dx[8]={1,1,2,2,-1,-1,-2,-2};int dy[8]={-2,2,-1,1,2,-2,1,-1};int DP(int x,int y){    int &m=dp[x][y];    if(m)  return m;    m=1;    for(int i=0;i<8;i++)    {        int nx=x+dx[i];        int ny=y+dy[i];        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&M[nx][ny]>M[x][y])        {            if(DP(nx,ny)+1>m)            {                m=DP(nx,ny)+1;                path[x][y]=mp(nx,ny);            }            else if(DP(nx,ny)+1==m&&M[path[x][y].fs][path[x][y].se]>M[nx][ny]) path[x][y]=mp(nx,ny);        }    }    return m;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++) scanf("%d",&M[i][j]);    int Max=1;    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++)    {        if(Max<DP(i,j))        {            Max=DP(i,j);            v.clear();            v.pb(mp(i,j));        }        else if(Max==DP(i,j)) v.pb(mp(i,j));    }    int key,keyx,keyy;    key=INF;    for(int i=0;i<v.size();i++)    {        if(key>M[v[i].fs][v[i].se])        {            key=M[v[i].fs][v[i].se];            keyx=v[i].fs;            keyy=v[i].se;        }    }    printf("%d\n",Max);    while(true)    {        printf("%d\n",key);        int fis=path[keyx][keyy].fs,sec=path[keyx][keyy].se;        keyx=fis;keyy=sec;        key=M[keyx][keyy];        if(!keyx) break;    }    return 0;}

 

POJ2111 Millenium Leapcow