题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1605
题意：
平面直角坐标系中，有n个点，m个标记（坐标范围1~1000）。
你可以发出口令，让所有点整体向东、南、西、北四个方向中的任意一个方向移动，口令分别记作'E','S','W','N'。
每当一个点碰到一个标记，则答案+1。（保证初始时没有点在标记上）
你最多可以发出t次口令。
问你答案最大是多少，并输出字典序最小的口令序列。
题解:
表示状态：
dp[i][j][k] = max survivors
i：水平方向共移动了i个单位（左负右正）
j：竖直方向共移动了j个单位（下负上正）
k：发了k次口令
（因为数组下标有负数，所以最后再给i,j统一加上30就好啦，现在先不管它）
找出答案：
max dp[i][j][k]
如何转移：
先预处理cnt数组：cnt[x][y]表示移动了(x,y)时，碰到标记的点的个数。
dp[x][y][k] = cnt[x][y] + max dp[lx][ly][k-1]
lx=i-dx[p], ly=j-dy[p] (p = 0 to 3)
边界条件：
dp[0][0][0] = 0
others = -INF（不存在）
输出序列：
说明：
（1）feas[x][y][k]，用来判断最终答案是否由状态(x,y,k)转移而来。
（2）way[x][y][k]，表示在状态(x,y,k)时发出的口令。
总共三步：
（1）先将feas全部设为false，再将最终答案的feas改为true。
（2）枚举k（从大到小）,i,j，判断当前(i,j,k)是否能转移到最终答案。如果能，更新当前way和feas。
（3）枚举k（从小到大），当前位置为(x,y)，输出way[x][y][k]，并更新(x,y)。
AC Code:
// state expression:
// dp[i][j][k] = max survivors
// i,j: moving dist
// k: whistling times
//
// find the answer:
// max dp[i][j][t]
//
// transferring:
// dp[x][y][k] = cnt[x][y] + max dp[lx][ly][k-1]
//
// boundary:
// dp[0][0][0] = 0
// others = -INF
//
// find the way:
// if dp[nx][ny][k+1] == cnt[nx][ny] + dp[x][y][k] and feas[nx][ny][k+1]
// way[x][y][k] = c[p]
// feas[x][y][k] = true
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_N 1005
#define MAX_T 65
#define MAX_K 35
#define INF 10000000 using namespace std; const int dx[]={,,,-};
const int dy[]={,,-,};
const char c[]={'E','N','S','W'}; int n,m,t;
int ans=;
int cx[MAX_N];
int cy[MAX_N];
int gx[MAX_N];
int gy[MAX_N];
int cnt[MAX_T][MAX_T];
int dp[MAX_T][MAX_T][MAX_K];
bool feas[MAX_T][MAX_T][MAX_K];
char way[MAX_T][MAX_T][MAX_K]; void read()
{
cin>>n>>m>>t;
for(int i=;i<n;i++)
{
cin>>cx[i]>>cy[i];
}
for(int i=;i<m;i++)
{
cin>>gx[i]>>gy[i];
}
} void cal_cnt()
{
memset(cnt,,sizeof(cnt));
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
int x=gx[j]-cx[i];
int y=gy[j]-cy[i];
if(abs(x)+abs(y)<=t) cnt[x+][y+]++;
}
}
} void cal_dp()
{
for(int k=;k<=t;k++)
{
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
dp[i][j][k]=-INF;
}
}
}
dp[][][]=;
for(int k=;k<=t;k++)
{
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(i+j->t) continue;
for(int p=;p<;p++)
{
int lx=i-dx[p];
int ly=j-dy[p];
dp[i][j][k]=max(dp[i][j][k],cnt[i][j]+dp[lx][ly][k-]);
}
ans=max(ans,dp[i][j][k]);
}
}
}
} void cal_way()
{
memset(feas,false,sizeof(feas));
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(dp[i][j][t]==ans) feas[i][j][t]=true;
}
}
for(int k=t-;k>=;k--)
{
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
for(int p=;p<;p++)
{
int nx=i+dx[p];
int ny=j+dy[p];
if(dp[nx][ny][k+]==cnt[nx][ny]+dp[i][j][k] && feas[nx][ny][k+])
{
way[i][j][k]=c[p];
feas[i][j][k]=true;
break;
}
}
}
}
}
} void solve()
{
cal_cnt();
cal_dp();
cal_way();
} void print()
{
cout<<ans<<endl;
int x=;
int y=;
for(int k=;k<t;k++)
{
cout<<way[x][y][k];
for(int p=;p<;p++)
{
if(way[x][y][k]==c[p])
{
x+=dx[p];
y+=dy[p];
break;
}
}
}
} int main()
{
read();
solve();
print();
}