首页 > 代码库 > [COJ0988]WZJ的数据结构（负十二）
[COJ0988]WZJ的数据结构（负十二）
[COJ0988]WZJ的数据结构（负十二）
试题描述
输入
见题目，注意本题不能用文件输入输出
输出
见题目，注意本题不能用文件输入输出
输入示例
4100000010000000041 11 21 31 4
输出示例
0121
数据规模及约定
1≤N≤1500，M≤N×N 且 M≤300000。
题解
我们先预处理出 d[i][j] 表示距离 (i, j) 这个点最近的点（只考虑第 i 行）的欧几里得距离。那么我们可以枚举行数 i，然后变成一维问题从左往右扫，设 f(i, j) 为离该点最近的点的欧几里得距离（即答案），那么有 f(i, j) = min{ d[i][k] + (j - k)2 | 1 ≤ k ≤ j }，显然可以用斜率优化来搞。
#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <stack>#include <vector>#include <queue>#include <cstring>#include <string>#include <map>#include <set>using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++;}int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f;}#define maxn 1510#define oo 2147483647int n, d[maxn][maxn], f[maxn][maxn];char Map[maxn][maxn];int sqr(int x) { return x * x; }struct Node { int x, y; Node() {} Node(int _, int __): x(_), y(__) {}} q[maxn];double slop(Node a, Node b) { return ((double)a.y - b.y) / ((double)a.x - b.x);}int main() { n = read(); for(int i = 1; i <= n; i++) scanf("%s", Map[i] + 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = oo; for(int j = 1; j <= n; j++) { int tmp = -1; for(int i = 1; i <= n; i++) { if(Map[i][j] == ‘1‘) tmp = i; if(tmp > 0) d[i][j] = min(d[i][j], sqr(i - tmp)); } tmp = -1; for(int i = n; i; i--) { if(Map[i][j] == ‘1‘) tmp = i; if(tmp > 0) d[i][j] = min(d[i][j], sqr(i - tmp)); } } for(int i = 1; i <= n; i++) { int ql = 1, qr = 0; for(int j = 1; j <= n; j++) { if(d[i][j] < oo) { Node t(j, d[i][j] + sqr(j)); while(ql < qr && slop(q[qr-1], q[qr]) > slop(q[qr], t)) qr--; q[++qr] = t; } while(ql < qr && slop(q[ql], q[ql+1]) < 2.0 * j) ql++; if(ql <= qr) f[i][j] = q[ql].y - 2 * j * q[ql].x + sqr(j);// printf("%d %d: %d\n", i, j, f[i][j]); } ql = 1; qr = 0; for(int j = n; j; j--) { if(d[i][j] < oo) { Node t(j, d[i][j] + sqr(j)); while(ql < qr && slop(q[qr-1], q[qr]) < slop(q[qr], t)) qr--; q[++qr] = t; } while(ql < qr && slop(q[ql], q[ql+1]) > 2.0 * j) ql++; if(ql <= qr) f[i][j] = min(f[i][j] ? f[i][j] : oo, q[ql].y - 2 * j * q[ql].x + sqr(j)); } } int q = read(); while(q--) { int a = read(), b = read(); printf("%d\n", f[a][b]); } return 0;}
[COJ0988]WZJ的数据结构（负十二）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。