◉ ABC274
// 枚举作为左端点的鱼
// 每条鱼有一个在这个区间中的时间段
// 计算出与长度为 a 的区间有交集的时间的区间的权值的最大值
// 时间的区间(离散化->)差分->每一段的权值的最大值
点击查看代码
Source Code
Copy
Copy
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 2005;
int n, a, w[N], x[N], v[N], res;
int main() {
scanf("%d%d", &n, &a);
for(int i = 1; i <= n; i ++) scanf("%d%d%d", w + i, x + i, v + i);
for(int i = 1; i <= n; i ++) {
int ans = 0;
std::map<double, int> d;
for(int j = 1; j <= n; j ++)
if(v[i] == v[j]) {
if(x[j] <= x[i] && x[i] <= x[j] + a) ans += w[j]; // 现在 ans 为与第 i 条鱼相对静止的鱼的权值和
} else {
double l = double(x[j] - x[i]) / (v[i] - v[j]), r = double(a + x[j] - x[i]) / (v[i] - v[j]);
if(l > r) std::swap(l, r);
if(r >= 0) d[std::max(l, 0.0)] += w[j], d[r + 1e-10] -= w[j];
}
res = std::max(res, ans);
for(auto [p, q] : d) res = std::max(res, ans += q);
}
printf("%d\n", res);
return 0;
}
// 转化为二分图最小点覆盖问题:使用二分图最大匹配
// 只用考虑朝向右边或下边的摄像头
// 建图: 每行每列找到所有最长连续的空地
// 建边: 对于所有空地, 将其在行中的编号和在列中的编号建边
// .#.# 1#2# 1#4#
// #... #333 #345
// ...# 444# 234#
// ##.# ##5# ##4#
点击查看代码
Source Code
Copy
Copy
#include <vector>
#include <stdio.h>
#include <string.h>
const int N = 302;
int n, m, p, q;
char g[N][N];
int id1[N][N], id2[N][N];
std::vector<int> e[N * N];
bool st[N * N]; int match[N * N];
bool find(int x) {
for(int y : e[x])
if(!st[y]) {
st[y] = true;
if(match[y] == -1 || find(match[y])) {
match[y] = x; return true;
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);
for(int i = 1; i <= n; i ++) {
if(g[i-1][m] != '#') ++ p;
for(int j = 1; j <= m; j ++)
if(g[i][j] == '.') id1[i][j] = p;
else if(g[i][j-1] != '#') ++ p;
}
for(int j = 1; j <= m; j ++) {
if(g[n][j-1] != '#') ++ q;
for(int i = 1; i <= n; i ++)
if(g[i][j] == '.') id2[i][j] = q;
else if(g[i-1][j] != '#') ++ q;
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
if(g[i][j] == '.') e[id1[i][j]].push_back(id2[i][j]);
memset(match, -1, sizeof(match));
int res = 0;
for(int i = 1; i <= p; i ++) {
if(i != 1) memset(st, 0, sizeof(st));
if(find(i)) res ++;
}
printf("%d\n", res);
return 0;
}