题解 P2905 【[USACO08OPEN]农场危机Crisis on the Farm】

· · 题解

作为此题目前的最优解，我有必要发一个新的题解：

首先，本题的情景是平面直角坐标系，

分析一下可知要用dp,

设f[i][j][k]为前i秒向北移动j步，向东移动k步最多能挽救的奶牛数

则f[i][j][k]=max(f[i-1][j+1][k],f[i-1][j][k+1],f[i-1][j-1][k],f[i-1][j][k-1])+g[j][k]

而g[j][k]表示全体奶牛向北移动j步，向东移动k步时能挽救的奶牛数

给出代码：

#include<cstdio>
const int N=1000,T=31;
const int dx[]={1,0,0,-1},dy[]={0,1,-1,0},d[]={69,78,83,87};
//方向增量按字母字典序的顺序给出：E,N,S,W
int n,m,k,i,j,s,t,x[N],y[N],p[N],q[N],g[T*2][T*2],f[T][T*2][T*2],u,v;
//因为下标不能为负，所以向南向西的负数要加上T使之为正
int max(int x,int y){return x>y?x:y;}
int abs(int x){return x>0?x:-x;}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<n;i++)
        scanf("%d%d",x+i,y+i);
    for(i=0;i<m;i++)
        scanf("%d%d",p+i,q+i);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(abs(p[j]-x[i])+abs(q[j]-y[i])<=k)
                g[p[j]-x[i]+T][q[j]-y[i]+T]++;
    //g数组由初始化得到，只要奶牛和草垛的曼哈顿距离<=k,便是可达的
    for(t=k;t>=0;t--)//阶段从大到小枚举是为了输出使字典序最小方便
        for(u=T-t;u<=T+t;u++)
            for(v=T-t;v<=T+t;v++){
                for(i=0;i<4;i++)
                    f[t][u][v]=max(f[t+1][u+dx[i]][v+dy[i]],f[t][u][v]);
                f[t][u][v]+=g[u][v];
            }
    printf("%d\n",f[0][T][T]);
    u=T;v=T;
    for(i=0;i<k;i++){
        for(j=0;j<4;j++)
            if(f[i][u][v]==f[i+1][u+dx[j]][v+dy[j]]+g[u][v])
                break;
        //只要发现本状态是由第j个决策得来的就退出循环，输出
        u+=dx[j];v+=dy[j];
        printf("%c",d[j]);
    }
    return 0;
}
//时间复杂度：O(n*m+k^3)
//空间复杂度：O(n+m+k^3)