题目描述
约翰和他的奶牛组建了一只乐队“后街奶牛”，现在他们正在牧场里排练.奶牛们分成一堆 一堆，共1000)堆.每一堆里，30只奶牛一只踩在另一只的背上，叠成一座牛塔.牧场 里还有M(1 < M < 1000)个高高的草垛.
作为出色的指挥家，约翰可以通过口哨指挥奶牛们移动.他的口哨有四个音，分别能使所有 的牛塔向东南西北四个方向移动一格.
每一次，当一个牛塔到达了一个草垛所在的格子，牛塔最上方的奶牛就会跳到草垛上，而且 不再下来，而其他奶牛仍然呈塔状站在草垛所在的格子里.当牛塔只剩一只奶牛时，这只奶牛也 会跳到草垛上.
突然，约翰大惊失色：原来邻家的奶缸爆炸了！滚滚而下的牛奶正朝着约翰的牧场冲来，不久就要将牧场淹没.约翰必须马上行动，用口哨声挽救奶牛们的生命.他要指挥奶牛尽量多地跳 上草操，草操上的奶牛将不会被淹死.
约翰还有K次吹口哨的机会.那他最多还能救多少奶牛呢？请计算最多能挽救的奶牛数，以及 达到这个数目约翰需要吹的口哨调子序列.序列用E，W,S，N表示东西南北.如果有多种序列能达到 要求，输出作为字符串最小的.
输入输出格式
输入格式：
-
Line 1: Three space-separated integers: N, M, and K
-
Lines 2..N+1: Line i+1 describes the X,Y location of a stack of 30 cows using two space-separated integers: X_i and Y_i
- Lines N+2..N+M+1: Line i+N+1 describes the X,Y location of a haystack using two space-separated integers: X_i and Y_i
输出格式：
-
Line 1: A single integer that is the most number of cows that can be saved.
- Line 2: K characters, the lexicographically least sequence of commands FJ should issue to maximize the number of cows saved.
输入输出样例
3 6 3 3 4 6 2 5 7 8 2 9 2 6 4 5 4 6 7 8 7
6 EEE
说明
Use the 'east' whistle three times, at which point the milk floods the area. Each haystack ends up saving 1 cow.
dp 恶心。。
一个神奇的问题：
考试时我读不完数据 (#‵′)靠
前面的很正常
m个草都是0的读不完。。
读入优化超时
cin scanf读不进去 直接炸内存。。
#include <cstring> #include <cstdio> #define N 35 #define M 2005 #define INF 0x3f3f3f3f int n,m,k,ans=0,x[M],y[M],li=31,lj=31,f[N<<2][N<<2][N],newmap[N<<2][N<<2],Map[M][M],fx[5]={-1,0,0,1},fy[5]={0,-1,1,0}; char pre[N<<2][N<<2][N],pick[N]; inline int max(int a,int b) {return a>b?a:b;} void init_map() { for(int i=0;i<=62;i++) { for(int j=0;j<=62;j++) { for(int l=1;l<=n;l++) { int X=x[l],Y=y[l]; if(X+i-31<=0||Y+j-31<=0||X+i-31>1000||Y+j-31>1000) continue; newmap[i][j]+=Map[X+i-31][Y+j-31]; } } } } int main() { // freopen("dance.in","r",stdin);freopen("dance.out","w",stdout); pick[0]='W',pick[1]='S',pick[2]='N',pick[3]='E'; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); for(int x,y,i=1;i<=m;i++) { scanf("%d%d",&x,&y); Map[x][y]++; } init_map(); for(int i=0;i<=k;i++) for(int j=0;j<=62;j++) for(int l=0;l<=62;l++) f[j][l][i]=-INF,pre[j][l][i]='Z'; f[31][31][0]=0; for(int i=1;i<=k;i++) { for(int j=1;j<=61;j++) { for(int l=1;l<=61;l++) { f[j][l][i]=max(max(f[j-1][l][i-1],f[j][l-1][i-1]),max(f[j][l+1][i-1],f[j+1][l][i-1]))+newmap[j][l]; if(i==k) ans=max(ans,f[j][l][i]); } } } for(int i=1;i<=61;i++) for(int j=1;j<=61;j++) if(f[i][j][k]==ans) pre[i][j][k]='A'; for(int l=k-1;l>=0;l--) { for(int i=1;i<=61;i++) { for(int j=1;j<=61;j++) { for(int o=0;o<4;o++) { if(f[i][j][l]+newmap[i+fx[o]][j+fy[o]]==f[i+fx[o]][j+fy[o]][l+1]&&pre[i+fx[o]][j+fy[o]][l+1]<'Z') pre[i][j][l]=pick[o]; } } } } printf("%d ",ans); for(int i=0;i<k;i++) { printf("%c",pre[li][lj][i]); if(pre[li][lj][i]=='E') li++; else if(pre[li][lj][i]=='N') lj++; else if(pre[li][lj][i]=='S') lj--; else if(pre[li][lj][i]=='W') li--; } return 0; }