首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。