uoj240 【IOI2016】aliens

uoj240 【IOI2016】aliens

​​ 题目：​​​对称 然后 把明显可以被其他覆盖的点去掉

剩下的点考虑用三角形覆盖

然后剩下的点按照x从小到大排序 这时候其实y也是从小到大了

设dp[i][k]表示当前在做第i个三角形 已经拍照k张的最小覆盖格子是多少

可以斜率优化复杂度下降到n*k

然后就二分一个权值没多分一块就加一个这样权值特别大只分一块 i直到刚好卡到k位置

这题注意大概因为有重复的所以还需要在计算的时候把他们都减去才可以！！

#include "aliens.h"#include #include #include#define ll long longusing namespace std;const int N=100010;struct node{ int x,y;}p[N],p1[N];inline bool cmp(const node &a,const node &b){return a.xcalc(q[cl]+1,i+1)) --cl;q[++cl]=i; }return num[n];}long long take_photos(int n, int m, int k, std::vector r, std::vector c) { for (int i=0;ic[i]) swap(p[i+1].x,p[i+1].y);} sort(p+1,p+n+1,cmp);ll l1=0,r1=(ll)m*m; for (int i=1;i<=n;++i){ while(top&&p[i].y<=p1[top].y) --top; p1[++top]=p[i]; }n=top;for (int i=1;i<=n;++i) p[i]=p1[i]; if (n<=k) { for (int i=1;i<=n;++i) {ans+=sqr(p[i].x-p[i].y+1); if (i>1; if (gao(mid,n)<=k) ans=dp[n],r1=mid-1;else l1=mid+1; }return ans-l1*k; //printf("%lld\n",ans-l1*k);}int main() { freopen("ex_aliens1.in","r",stdin); int n, m, k; assert(3 == scanf("%d %d %d", &n, &m, &k)); std::vector r(n), c(n); for (int i = 0; i < n; i++) { assert(2 == scanf("%d %d", &r[i], &c[i])); } long long ans = take_photos(n, m, k, r, c); printf("%lld\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。