P2905 [USACO08OPEN]农场危机Crisis on the Farm
发现总步数$k<=30$，考虑用$k$瞎搞
设$f[u][i][j]$表示已经吹$u$次哨，全体奶牛向右走$i$步，向上走$j$步的最优解
预处理$g[i][j]$表示全体奶牛向右走$i$步，向上走$j$步可以救几只奶牛
显然$f[u][i][j]=max(f[u+1][i+1][j],f[u+1][i-1][j],f[u+1][i][j+1],f[u+1][i][j-1])+g[i][j]$
把方向按字典序，逆推。
end.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cctype> 5 #define re register 6 using namespace std; 7 void read(int &x){ 8 char c=getchar();x=0; 9 while(!isdigit(c)) c=getchar(); 10 while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); 11 } 12 int max(int a,int b){return a>b?a:b;} 13 int abs(int a){return a<0?-a:a;} 14 #define K 31 15 #define N 1001 16 const int d1[4]={-1,0,0,1}; 17 const int d2[4]={0,-1,1,0};//方向倒着来因为后面用的是逆推 18 const char d3[4]={'E','N','S','W'}; 19 struct node{int x,y;}a[N],b[N]; 20 int n,m,k,g[K<<1][K<<1],f[K+1][K<<1][K<<1];//坐标为负的话加上一个maxk转正 21 int main(){ 22 read(n);read(m);read(k); 23 for(re int i=1;i<=n;++i) read(a[i].x),read(a[i].y); 24 for(re int i=1;i<=m;++i) read(b[i].x),read(b[i].y); 25 for(re int i=1;i<=n;++i)//预处理g数组 26 for(re int j=1;j<=m;++j) 27 if(abs(a[i].x-b[j].x)+abs(a[i].y-b[j].y)<=k) 28 ++g[a[i].x-b[j].x+K][a[i].y-b[j].y+K]; 29 for(re int u=k;u>=0;--u)//逆推好写 30 for(re int i=K-u;i<=K+u;++i) 31 for(re int j=K-u;j<=K+u;++j){ 32 for(int z=0;z<4;++z) 33 f[u][i][j]=max(f[u][i][j],f[u+1][i+d1[z]][j+d2[z]]); 34 f[u][i][j]+=g[i][j]; 35 } 36 printf("%d ",f[0][K][K]); 37 int x0=K,y0=K; 38 for(re int u=0,z;u<k;++u){ 39 for(z=0;z<4;++z) 40 if(f[u][x0][y0]==f[u+1][x0+d1[z]][y0+d2[z]]+g[x0][y0]) 41 break;//发现是这个状态转移来的就跳出 42 printf("%c",d3[z]); 43 x0+=d1[z]; y0+=d2[z]; 44 }return 0; 45 }