BZOJ1605 [Usaco2008 Open]Crisis on the Farm 牧场危机
2024-10-08 13:26:57
标题好长&&我是权限狗,汪汪!
题没看懂的我以为这是一道极难滴题目。。。然后,然后我就看懂题了。
数据少给了一个条件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 ;
}
比某些斜率优化还长。。。
最新文章
- 我的屌丝giser成长记-研一篇(下)
- 为什么我们拿Fork当收藏用
- 【2016-11-6】【坚持学习】【Day21】【子窗口关闭时,同步关闭它的主窗口(方法二)】
- jprofiler_监控远程linux服务器的tomcat进程(实践)
- 学习MySQL之数据库操作(一)
- vi 技巧和诀窍~转IBM
- 第八篇.Bootstrap下拉菜单
- spring代理模式 service远程调用,插件执行
- c++中关于初始化型参列表的一些问题
- 消息提示插件toastr.js与Messenger组件
- Codeforces Round #345 (Div. 2)
- C++去掉字符串首尾的 空格 换行 回车
- 『设计前沿』14款精致的国外 iOS7 图标设计示例
- 数据库MySql阶段总结
- C++ Code_HotKey
- Integer Intervals(贪心)
- Android 连接Wifi和创建Wifi热点 demo
- STL MAP 反序迭代
- OpenCV:二值图像连通区域分析与标记算法实现
- MongoDB中的映射,限制记录和记录拼排序 文档的插入查询更新删除操作
热门文章
- tf.random_uniform的使用
- 我们能从 jQuery 的一个正则表达式中学到什么?
- Python3基础 super 子类调用父类的__init__
- ubuntu16.04下无线网卡无法正常连网
- Java基础部分二
- HDU1698 Just a Hook(线段树&;区间覆盖)题解
- K条最短路径算法(KSP, k-shortest pathes):Yen&#39;s Algorithm
- U盘中病毒了怎么办
- Struts2 文件下载(中文处理方法以及控制下载文件名称和扩展名)
- ros python 重置位置