P2905 [USACO08OPEN]农场危机Crisis on the Farm

传送门

DP

设 f [ i ] [ j ] [ k ] 表示已经走了 i 步，向上走了 j 步，向右走了 k 步时能拯救的最多奶牛数（j，k可以为负，表示反向）

设 g [ i ] [ j ] 表示牛向上走 i 步，向右走 j 步后有多少奶牛恰好在草堆上（同样 i , j 可负）

那么 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 ]

因为数组下标不能为负，所以要把坐标集体加上一个 K

为了方便按字典序输出，我们要倒过来推，并且要按字典序的方向来枚举

即从 f [ k ] 推到 f [ 0 ] 枚举方向为 'E' 'N' 'S' 'W'

好像不太好讲，具体还是看代码吧，代码不难的

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=,K=;

int n,m,k;

int xx[]={,,,-},yy[]={,,-,};

char mp[]={'E','N','S','W'};

int f[K<<][N][N],g[K<<][K<<];

int cow[N][],hay[N][];

int main()

{

    n=read(); m=read(); k=read();

    for(int i=;i<=n;i++) cow[i][]=read(),cow[i][]=read();

    for(int i=;i<=m;i++) hay[i][]=read(),hay[i][]=read();

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            if(abs(hay[j][]-cow[i][])+abs(hay[j][]-cow[i][])<=k)//如果可以到达才计算贡献

                g[hay[j][]-cow[i][]+K][hay[j][]-cow[i][]+K]++;//预处理g

    for(int i=k;i>=;i--)

        for(int x=K-i;x<=K+i;x++)

            for(int y=K-i;y<=K+i;y++)//注意大小写K的区别

            {

                for(int o=;o<;o++) f[i][x][y]=max(f[i][x][y],f[i+][x+xx[o]][y+yy[o]]);

                f[i][x][y]+=g[x][y];

            }

    printf("%d\n",f[][K][K]);

    int posx=K,posy=K;//存当前位置

    for(int i=;i<k;i++)

    {

        int o;

        for(o=;o<;o++) if(f[i][posx][posy]==f[i+][posx+xx[o]][posy+yy[o]]+g[posx][posy]) break;//如果是从o推过来的就断开

        posx+=xx[o]; posy+=yy[o];

        printf("%c",mp[o]);

    }

    return ;

}