|
Posted on 2010-07-15 21:10 Uriel 阅读(442) 评论(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; }
|