Description
约翰和他的奶牛组建了一只乐队“后街奶牛”，现在他们正在牧场里排练．奶牛们分成一堆一堆，共N(1≤N≤1000)堆．每一堆里，30只奶牛一只踩在另一只的背上，叠成一座牛塔．牧场里还有M(1≤M≤1000)个高高的草垛． 作为出色的指挥家，约翰可以通过口哨指挥奶牛们移动．他的口哨有四个音，分别能使所有的牛塔向东南西北四个方向移动一格．
每一次，当一个牛塔到达了一个草垛所在的格子，牛塔最上方的奶牛就会跳到草垛上，而且不再下来，而其他奶牛仍然呈塔状站在草垛所在的格子里．当牛塔只剩一只奶牛时，这只奶牛也会跳到草垛上． 突然，约翰大惊失色：原来邻家的奶缸爆炸了！滚滚而下的牛奶正朝着约翰的牧场冲来，不久就要将牧场淹没．约翰必须马上行动，用口哨声挽救奶牛们的生命．他要指挥奶牛尽量多地跳上草垛，草垛上的奶牛将不会被淹死． 约翰还有K次吹口哨的机会．那他最多还能救多少奶牛呢？请计算最多能挽救的奶牛数，以及达到这个数目约翰需要吹的口哨调子序列．序列用E，W，S，N表示东西南北．如果有多种序列能达到
要求，输出作为字符串最小的．
Input
第1行输入三个整数N，M，K，之后N行每行输入一对整数(Xi，Yi)表示一座牛塔所在的位置，1<=K<=30
之后M行每行输入一对整数(Xi，Yi)表示一个草垛所在的位置．1≤Xi≤1000;1≤Yi≤1000.
Output
第1行输出最多能挽救的奶牛数．第2行输出口哨调子序列．
Sample Input
3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7
Sample Output
Use the ‘east’ whistle three times, at which point the milk floods
the area. Each haystack ends up saving 1 cow.
6
EEE
题解：
这道题真的是超级麻烦，思想上非常好想，就是一个DP加方案的输出，但是这题无论是预处理还是最后方案输出都比较麻烦，WA了很久都是方案输出的问题。
首先要注意的是K是在30以内的，所以不用去考虑那个牛塔没牛的情况，那么我们先预处理一下在移动delta(x)，delta(y)的情况下，能够有多少的牛到草棚上，记为get[x][y]。
然后dp数组为3维的，分别为x，y，k，也就是说dp[i][j][t]是在第t次移动后，总共移动为i，j的最大权值（即最大获救牛数量）。所以可以很轻松的写出状态转移方程：dp[i][j][t]=max(dp[i+1][j][t-1],dp[i+1][j][t-1],dp[i][j-1][t-1],dp[i][j+1][t-1])+get[i][j]。那么就能轻松得到最大权值了。
接下来是讨厌的方案输出，由于非常容易有多个解，此题要求输出字典序最小的方案，那么我们可以知道东南西北的英文缩写的字典序为E,N,S,W。由于我们要倒着来求方案，所以也按着W,S,N,E的顺序来规划局部方案，这样最后得到的就是字典序最小的了。
有些地方没做处理，最后跑了48ms，还算勉强。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int n,m,k;
typedef struct node
{int x,y;
} node;
node cow[1005];
bool grass[1005][1005];
int get[105][105];
int dp[105][105][35];
char Turn(int x,int y)
{if(x==-1)return 'W';if(x==1)return 'E';if(y==-1)return 'S';return 'N';
}
int moved[4][2]= {
{
1,0},{
0,1},{
0,-1},{-1,0}};
bool check(int x,int y)
{if(x<0 || x>1000 || y<0 || y>1000)return 0;return 1;
}
char pre[105][105][35];
char nn[4]= {
'E','N','S','W'};
int main()
{int x,y;cin >> n >> m >> k;int fix=k+1;for(int i=0; i<n; i++)scanf("%d%d",&cow[i].x,&cow[i].y);for(int i=0; i<m; i++){scanf("%d%d",&x,&y);grass[x][y]=1;}for(int i=1; i<=2*k+1; i++)for(int j=1; j<=2*k+1; j++){if(abs(i-fix)+abs(j-fix)>k)continue;for(int z=0; z<n; z++){x=cow[z].x+i-fix,y=cow[z].y+j-fix;if(!check(x,y))continue;if(grass[x][y])get[i][j]++;}}int out=0;for(int t=1; t<=k; t++)for(int i=1; i<=2*k+1; i++)for(int j=1; j<=2*k+1; j++){int tmp=abs(i-fix)+abs(j-fix);if(tmp>t)continue;if(tmp==t || (t-tmp)%2==0){dp[i][j][t]=max(max(dp[i-1][j][t-1],dp[i+1][j][t-1]),max(dp[i][j-1][t-1],dp[i][j+1][t-1]))+get[i][j];if(t==k && dp[i][j][t]>=out)out=dp[i][j][t];}}for(int i=1; i<=2*k+1; i++)for(int j=1; j<=2*k+1; j++)if(dp[i][j][k]==out)pre[i][j][k]='F';cout << out << endl;for(int t=k-1; t>=0; t--)for(int i=1; i<=2*k+1; i++)for(int j=1; j<=2*k+1; j++){int tmp=abs(i-fix)+abs(j-fix);if(tmp>t)continue;for(int z=3; z>=0; z--)if(dp[i][j][t]+get[i+moved[z][0]][j+moved[z][1]]==dp[i+moved[z][0]][j+moved[z][1]][t+1] && pre[i+moved[z][0]][j+moved[z][1]][t+1]!=0)pre[i][j][t]=nn[z];}int nowx=fix,nowy=fix;for(int i=0; i<k; i++){printf("%c",pre[nowx][nowy][i]);switch(pre[nowx][nowy][i]){case 'E':nowx++;break;case 'N':nowy++;break;case 'S':nowy--;break;case 'W':nowx--;break;}}return 0;
}