注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2111Millenium Leapcow题解  

2014-03-25 20:27:30|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

leapcow

BY   LGS

题目大意:给你一个N*N的矩阵,求从某个点开始到某个点结束的一条高度上升序列,每次只能走与当前这个点马子步的下一个点.使这条序列最长.


题解:类似于滑雪,先将高度排序好后顺带每个点坐标.那么就成了最长不降序列.本来的条件A[I]<A[J]就变成了I,J相邻.然而这样做还是(N*N)^2=N^4.那么我们是否可以进行优化?直接从马字步扩展过来.,可以在DP时用数组记录下F[X][Y]的最小值即可,xy表示坐标.

 

总结:DP.

代码:

#include<cstdio>
#include<algorithm>
#define maxn 400
using namespace std;
struct node{
int x,y,s;
}a[maxn*maxn];
int i,j,n,k,x,y,xx,yy,ans,anss;
int f[maxn*maxn],pre[maxn*maxn],p[maxn][maxn];
int abs(int w){return (w>0)?w:(-w);}
const int han[9]={0,-2,-2,-1,-1,1,1,2,2};
const int lie[9]={0,-1,1,-2,2,-2,2,-1,1};
bool cmp(const node &a,const node &b){return a.s<b.s;}
int main()
{
 scanf("%d",&n);
 for (i=1;i<=n;i++)
  for (j=1;j<=n;j++){
      scanf("%d",&p[i][j]);
      a[++k].s=p[i][j];
      a[k].x=i;a[k].y=j;
                    }
sort(a+1,a+k+1,cmp);
for (i=1;i<=k;i++) f[i]=1;
for (i=k-1;i>=1;i--)
             { 
             x=a[i].x;y=a[i].y;    
 for (j=1;j<=8;j++){
                    xx=x+han[j];yy=y+lie[j];    
            if ((xx>0)&&(xx<=n)&&(yy>0)&&(yy<=n))
                      if (i<p[xx][yy])
                           if ((f[i]<f[p[xx][yy]]+1)
  ||((f[i]==f[p[xx][yy]]+1)&&(pre[i]>p[xx][yy])))
                            {
                            f[i]=f[p[xx][yy]]+1;
                            pre[i]=p[xx][yy];
                            }
                   }
             }
 ans=-1;
for (i=1;i<=k;i++) if (f[i]>ans){ans=f[i];anss=i;}
printf("%d\n",ans);
while (anss){printf("%d\n",anss);anss=pre[anss];}
return 0;  
}

  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018