首页 > 代码库 > BZOJ1605 [Usaco2008 Open]Crisis on the Farm 牧场危机
BZOJ1605 [Usaco2008 Open]Crisis on the Farm 牧场危机
标题好长&&我是权限狗，汪汪！
题没看懂的我以为这是一道极难滴题目。。。然后，然后我就看懂题了。
数据少给了一个条件K <= 30...(没这条件还做个鬼。。。)
f[k, i, j]表示走了k步，x方向移动i，y方向移动j的最大被拯救牛的数量，然后方程就很好写了，略之。
（其实是太烦了，不想写）
真是一道很烦的题目。。。不仅预处理很烦，转移很烦，连输出解也很烦。。。
1 /************************************************************** 2 Problem: 1605 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:76 ms 7 Memory:1644 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 #define rep(i, n) for (int (i) = 1; (i) <= (n); ++(i))14 using namespace std;15 const int dx[5] = {0, 1, 0, 0, -1};16 const int dy[5] = {0, 0, 1, -1, 0};17 const int inf = (int) 1e9;18 const char CHAR[5] = {‘A‘, ‘W‘, ‘S‘, ‘N‘, ‘E‘};19 int n, m, K, ans;20 int Cx[1500], Cy[1500], Hx[1500], Hy[1500];21 int f[40][64][64], cnt[64][64];22 char step[40][64][64];23 24 int main(){25 scanf("%d%d%d", &n, &m, &K);26 rep(i, n)27 scanf("%d%d", Cx + i, Cy + i);28 rep(i, m)29 scanf("%d%d", Hx + i, Hy + i);30 rep(i, n) rep(j, m){31 int Dx = Cx[i] - Hx[j], Dy = Cy[i] - Hy[j];32 if (abs(Dx) <= 30 && abs(Dy) <= 30)33 ++cnt[31 + Dx][31 + Dy];34 }35 for (int k = 0; k <= K; ++k)36 for (int i = 0; i <= 62; ++i)37 for (int j = 0; j <= 62; ++j){38 f[k][i][j] = -inf;39 step[k][i][j] = ‘Z‘;40 }41 f[0][31][31] = 0;42 43 rep(k, K) rep(i, 61) rep(j, 61)44 f[k][i][j] = cnt[i][j] + max(max(f[k - 1][i - 1][j], f[k - 1][i + 1][j]), max(f[k - 1][i][j - 1], f[k - 1][i][j + 1]));45 ans = 0; 46 rep(i, 61) rep(j, 61)47 ans = max(ans, f[K][i][j]); 48 rep(i, 61) rep(j, 61)49 if (f[K][i][j] == ans)50 step[K][i][j] = ‘A‘;51 for (int k = K - 1; k >= 0; --k)52 rep(i, 61) rep(j, 61) rep(l, 4)53 if (f[k][i][j] + cnt[i + dx[l]][j + dy[l]] == f[k + 1][i + dx[l]][j + dy[l]] && step[k + 1][i + dx[l]][j + dy[l]] < ‘Z‘)54 step[k][i][j] = CHAR[l];55 56 printf("%d\n", ans);57 int i = 31, j = 31;58 for (int k = 0; k < K; ++k){59 printf("%c", step[k][i][j]);60 if (step[k][i][j] == ‘E‘) --i; else61 if (step[k][i][j] == ‘W‘) ++i; else62 if (step[k][i][j] == ‘S‘) ++j; else63 if (step[k][i][j] == ‘N‘) --j;64 }65 printf("\n");66 return 0;67 }
比某些斜率优化还长。。。
BZOJ1605 [Usaco2008 Open]Crisis on the Farm 牧场危机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。