博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ1390 CEOI2008 Fences 凸包、Floyd最小环/DP
阅读量:5120 次
发布时间:2019-06-13

本文共 3189 字,大约阅读时间需要 10 分钟。


为了方便描述把固定点叫做白色点,Tree叫做黑色点

一种基于特殊性质的做法:

如果不算入选白色的权值,那么一定会选中所有白色点构成的凸包上的点,因为能够尽可能围更多的黑色点。然后我们在这个基础上删凸包上无用的白色点,就可以使得在围住尽可能多的黑色点的情况下白色点最少。

但是是否这就是最优解?我们考虑舍弃围住一个黑色点的情况。因为如果某个黑点在凸包中,那么一定存在三个凸包上的白色点,它们构成的三角形围住这个黑色点,使用三角剖分不难证明。所以舍弃一个黑色点最多只会舍弃三个白色点,而\(111 > 3 \times 20\),所以舍弃黑色点是不优的。

所以我们必须要在围住尽可能多的黑色点的情况下选择尽可能少的白色点。

我们认为凸包由其上所有点逆时针旋转构成,意味着对于一个向量\(i \rightarrow j\),如果它可能作为凸包的一部分,那么在上面求出的凸包中包含的所有黑点都在当前向量的左半平面内。

不妨设\(f_{i,j}=1\)表示向量\(i \rightarrow j\)可能作为凸包的一部分,那么我们要求的就是一个最小环,Floyd求最小环即可。

时间复杂度\(O(N^3)\),代码在下面


还有一种不基于\(20\)\(111\)的DP做法

\(f_{j,k}\)表示当前凸包中上凸包边界点为\(j\)、下凸包边界点为\(k\)时的最小权值,转移找到一个新的点\(l\)\(f_{j,l} = f_{j,k} + 20 - 111 * in_{j,k,l}\),其中\(in_{i,j,k}\)表示点\(i,j,k\)构成的三角形中黑点数量

\(in_{i,j,k}\)只需要算\(num_{i,j}\)表示端点为点\(i,j\)的线段下端的黑点数量然后稍微容斥一下即可。

代码没有


#include
#include
#include
#include
#include
//This code is written by Itstusing namespace std;struct vec{ int x , y; vec(int _x = 0 , int _y = 0) : x(_x) , y(_y){} vec operator +(vec a){return vec(x + a.x , y + a.y);} vec operator -(vec a){return vec(x - a.x , y - a.y);} int operator %(vec a){return x * a.y - y * a.x;} bool operator <(const vec a)const{return x < a.x || (x == a.x && y < a.y);}}blk[107] , wht[107];int stk[107] , ind[107] , floyd[107][107];int N , M , top , cnt , sum;bool in[107];void create(){ sort(blk + 1 , blk + N + 1); for(int i = 1 ; i <= N ; ++i){ while(top > 1 && ((blk[i] - blk[stk[top - 1]]) % (blk[stk[top]] - blk[stk[top - 1]])) >= 0) --top; stk[++top] = i; } for(int i = 1 ; i <= top ; ++i) ind[++cnt] = stk[i]; top = 0; for(int i = N ; i ; --i){ while(top > 1 && ((blk[i] - blk[stk[top - 1]]) % (blk[stk[top]] - blk[stk[top - 1]])) >= 0) --top; stk[++top] = i; } for(int i = 2 ; i < top ; ++i) ind[++cnt] = stk[i]; ind[++cnt] = ind[1];}void init(){ for(int i = 1 ; i <= M ; ++i){ bool f = 1; for(int j = 1 ; f && j < cnt ; ++j) f = (blk[ind[j + 1]] - blk[ind[j]]) % (wht[i] - blk[ind[j]]) > 0; if(!f) sum += 111; else in[i] = 1; }}bool check(int x , int y){ for(int i = 1 ; i <= M ; ++i) if(in[i] && (blk[y] - blk[x]) % (wht[i] - blk[x]) < 0) return 0; return 1;}int main(){#ifndef ONLINE_JUDGE freopen("C.in","r",stdin); freopen("C.out","w",stdout);#endif cin >> N >> M; for(int i = 1 ; i <= N ; ++i) cin >> blk[i].x >> blk[i].y; for(int i = 1 ; i <= M ; ++i) cin >> wht[i].x >> wht[i].y; create(); init(); if(sum == 111 * M){ cout << sum; return 0; } memset(floyd , 1 , sizeof(floyd)); for(int i = 1 ; i <= N ; ++i) for(int j = 1 ; j <= N ; ++j) if(i != j && check(i , j)) floyd[i][j] = 1; int ans = 1e9; for(int i = 1 ; i <= N ; ++i) for(int j = 1 ; j <= N ; ++j) for(int k = 1 ; k <= N ; ++k) if(j != i && k != i) floyd[j][k] = min(floyd[j][k] , floyd[j][i] + floyd[i][k]); for(int i = 1 ; i <= N ; ++i) ans = min(ans , floyd[i][i]); cout << ans * 20 + sum; return 0;}

转载于:https://www.cnblogs.com/Itst/p/10484782.html

你可能感兴趣的文章
Java泛型的基本使用
查看>>
1076 Wifi密码 (15 分)
查看>>
rsync
查看>>
noip模拟赛 党
查看>>
bzoj2038 [2009国家集训队]小Z的袜子(hose)
查看>>
Java反射机制及其Class类浅析
查看>>
Postman-----如何导入和导出
查看>>
移动设备显示尺寸大全 CSS3媒体查询
查看>>
图片等比例缩放及图片上下剧中
查看>>
【转载】Linux screen 命令详解
查看>>
background-clip,background-origin
查看>>
Android 高级UI设计笔记12:ImageSwitcher图片切换器
查看>>
Blog文章待看
查看>>
【Linux】ping命令详解
查看>>
对团队成员公开感谢博客
查看>>
java学习第三天
查看>>
python目录
查看>>
django+uwsgi+nginx+sqlite3部署+screen
查看>>
Andriod小型管理系统(Activity,SQLite库操作,ListView操作)(源代码下载)
查看>>
在Server上得到数据组装成HTML后导出到Excel。两种方法。
查看>>