Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

USACO 2008 OPEN Gold & EOJ 180---Cow Neighborhoods DP

Posted on 2010-07-15 21:10 Uriel 阅读(442) 评论(0)  编辑 收藏 引用 所属分类: DPECUST 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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理