标题好长&&我是权限狗，汪汪！
题没看懂的我以为这是一道极难滴题目。。。然后，然后我就看懂题了。
数据少给了一个条件K <= 30...(没这条件还做个鬼。。。)
f[k, i, j]表示走了k步，x方向移动i，y方向移动j的最大被拯救牛的数量，然后方程就很好写了，略之。
（其实是太烦了，不想写）
真是一道很烦的题目。。。不仅预处理很烦，转移很烦，连输出解也很烦。。。
/**************************************************************
Problem: 1605
User: rausen
Language: C++
Result: Accepted
Time:76 ms
Memory:1644 kb
****************************************************************/ #include <cstdio>
#include <algorithm> #define rep(i, n) for (int (i) = 1; (i) <= (n); ++(i))
using namespace std;
const int dx[] = {, , , , -};
const int dy[] = {, , , -, };
const int inf = (int) 1e9;
const char CHAR[] = {'A', 'W', 'S', 'N', 'E'};
int n, m, K, ans;
int Cx[], Cy[], Hx[], Hy[];
int f[][][], cnt[][];
char step[][][]; int main(){
scanf("%d%d%d", &n, &m, &K);
rep(i, n)
scanf("%d%d", Cx + i, Cy + i);
rep(i, m)
scanf("%d%d", Hx + i, Hy + i);
rep(i, n) rep(j, m){
int Dx = Cx[i] - Hx[j], Dy = Cy[i] - Hy[j];
if (abs(Dx) <= && abs(Dy) <= )
++cnt[ + Dx][ + Dy];
}
for (int k = ; k <= K; ++k)
for (int i = ; i <= ; ++i)
for (int j = ; j <= ; ++j){
f[k][i][j] = -inf;
step[k][i][j] = 'Z';
}
f[][][] = ; rep(k, K) rep(i, ) rep(j, )
f[k][i][j] = cnt[i][j] + max(max(f[k - ][i - ][j], f[k - ][i + ][j]), max(f[k - ][i][j - ], f[k - ][i][j + ]));
ans = ;
rep(i, ) rep(j, )
ans = max(ans, f[K][i][j]);
rep(i, ) rep(j, )
if (f[K][i][j] == ans)
step[K][i][j] = 'A';
for (int k = K - ; k >= ; --k)
rep(i, ) rep(j, ) rep(l, )
if (f[k][i][j] + cnt[i + dx[l]][j + dy[l]] == f[k + ][i + dx[l]][j + dy[l]] && step[k + ][i + dx[l]][j + dy[l]] < 'Z')
step[k][i][j] = CHAR[l]; printf("%d\n", ans);
int i = , j = ;
for (int k = ; k < K; ++k){
printf("%c", step[k][i][j]);
if (step[k][i][j] == 'E') --i; else
if (step[k][i][j] == 'W') ++i; else
if (step[k][i][j] == 'S') ++j; else
if (step[k][i][j] == 'N') --j;
}
printf("\n");
return ;
}
比某些斜率优化还长。。。