|
|
Posted on 2010-07-15 21:10 Uriel 阅读(450) 评论(0) 编辑 收藏 引用 所属分类: DP 、 ECUST OJ
原题地址： http://blog.imzzl.com/2010/05/382.html 暑假集训第二场倒数第二题，比赛的时候只有DY，LP，ZMJ，hqch四位大牛出了。。 后2h基本都在纠结这题，最后以WA结束，因为没看到路径不唯一时要输出字典序最小的。。= =。。不过赛后知道这里错了之后还是纠结了大半天。。 思路部分参考了这里： http://blog.imzzl.com/2010/05/382.html 但是有点问题：1.中途就要每次取字典序最小的，2.最后i,j还要二重循环遍历找字典序最小的 本菜ws的代码如下：
 #include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 100000000
struct Cow
   {
 int x,y;
 };
Cow p[100001];
int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0};
int dp[65][65][35],path[4],n,m,k,map[3010][3010],tx,ty,g[65][65],nres,xx;
char pt[63][63][33][33],res[4][35],rres[35],tmp[35],dir[5][2]={"E","N","S","W"};
int main()
{
int i,j,t,w,h,x,tp,fx,fy;
scanf("%d %d %d",&n,&m,&k);
for(i=0;i<n;i++)scanf("%d %d",&p[i].x,&p[i].y);
for(i=0;i<m;i++)
  {
scanf("%d %d",&tx,&ty);
map[tx][ty]=1;
 }
for(i=0;i<=2*k;i++)
for(j=0;j<=2*k;j++)
{
for(t=0;t<=k;t++)dp[i][j][t]=-INF;
tp=0;
for(w=0;w<n;w++)
if(p[w].x+i-k>=0 && p[w].y+j-k>=0 && map[p[w].x+i-k][p[w].y+j-k])tp++;
g[i][j]=tp;
}
dp[k][k][0]=0;
for(h=1;h<=k;h++)
for(i=k-h;i<=k+h;i++)
for(j=k-h;j<=k+h;j++)
{
for(w=0;w<4;w++)
if(i>=dx[w] && j>=dy[w] && dp[i-dx[w]][j-dy[w]][h-1]>dp[i][j][h])dp[i][j][h]=dp[i-dx[w]][j-dy[w]][h-1];
x=0;
for(w=0;w<4;w++)
if(i>=dx[w] && j>=dy[w] && dp[i-dx[w]][j-dy[w]][h-1]==dp[i][j][h])path[x++]=w;
dp[i][j][h]+=g[i][j];
nres=0;
for(w=0;w<x;w++)
{
strcpy(res[w],pt[i-dx[path[w]]][j-dy[path[w]]][h-1]);
strcat(res[w],dir[path[w]]);
if(strcmp(res[nres],res[w])>0)nres=w;
}
strcpy(pt[i][j][h],res[nres]);
}
tp=0;
for(i=0;i<=2*k;i++)
for(j=0;j<=2*k;j++)
if(dp[i][j][k]>tp)tp=dp[i][j][k];
fx=-1;fy=-1;
for(i=0;i<=2*k;i++)
for(j=0;j<=2*k;j++)
if(dp[i][j][k]==tp)
if(fx<0)
{
fx=i;fy=j;
}
else if(strcmp(pt[fx][fy][k],pt[i][j][k])>0)
{
fx=i;fy=j;
}
printf("%d\n",tp);
puts(pt[fx][fy][k]);
return 0;
}
|