标题好长&&我是权限狗,汪汪!

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

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

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

最新文章

  1. 我的屌丝giser成长记-研一篇(下)
  2. 为什么我们拿Fork当收藏用
  3. 【2016-11-6】【坚持学习】【Day21】【子窗口关闭时,同步关闭它的主窗口(方法二)】
  4. jprofiler_监控远程linux服务器的tomcat进程(实践)
  5. 学习MySQL之数据库操作(一)
  6. vi 技巧和诀窍~转IBM
  7. 第八篇.Bootstrap下拉菜单
  8. spring代理模式 service远程调用,插件执行
  9. c++中关于初始化型参列表的一些问题
  10. 消息提示插件toastr.js与Messenger组件
  11. Codeforces Round #345 (Div. 2)
  12. C++去掉字符串首尾的 空格 换行 回车
  13. 『设计前沿』14款精致的国外 iOS7 图标设计示例
  14. 数据库MySql阶段总结
  15. C++ Code_HotKey
  16. Integer Intervals(贪心)
  17. Android 连接Wifi和创建Wifi热点 demo
  18. STL MAP 反序迭代
  19. OpenCV:二值图像连通区域分析与标记算法实现
  20. MongoDB中的映射,限制记录和记录拼排序 文档的插入查询更新删除操作

热门文章

  1. tf.random_uniform的使用
  2. 我们能从 jQuery 的一个正则表达式中学到什么?
  3. Python3基础 super 子类调用父类的__init__
  4. ubuntu16.04下无线网卡无法正常连网
  5. Java基础部分二
  6. HDU1698 Just a Hook(线段树&amp;区间覆盖)题解
  7. K条最短路径算法(KSP, k-shortest pathes):Yen&#39;s Algorithm
  8. U盘中病毒了怎么办
  9. Struts2 文件下载(中文处理方法以及控制下载文件名称和扩展名)
  10. ros python 重置位置