BZOJ1605 [Usaco2008 Open]Crisis on the Farm 牧场危机

标题好长&&我是权限狗，汪汪！

题没看懂的我以为这是一道极难滴题目。。。然后，然后我就看懂题了。

数据少给了一个条件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 ;

 }

比某些斜率优化还长。。。