大兴网站开发网站建设价格,商城网站建设新闻,有限责任公司属于什么企业类型,天津网站建设诺亚传送门
题意#xff1a;一个x∈(−∞,∞),y∈[0,R]x\in(-\infin,\infin),y\in[0,R]x∈(−∞,∞),y∈[0,R]的矩形中有nnn个点#xff0c;矩形外有mmm个半径均为RRR的圆#xff0c;有独立的代价cic_ici。求覆盖最多的点所需的最小代价。 n,m≤100n,m\leq100n,m≤100
显然先…传送门
题意一个x∈(−∞,∞),y∈[0,R]x\in(-\infin,\infin),y\in[0,R]x∈(−∞,∞),y∈[0,R]的矩形中有nnn个点矩形外有mmm个半径均为RRR的圆有独立的代价cic_ici。求覆盖最多的点所需的最小代价。
n,m≤100n,m\leq100n,m≤100
显然先把永远不可能覆盖到的点扔掉然后转化为覆盖所有点
先考虑圆心都在矩形上方的情况
结论 对于一个合法即覆盖所有点的圆的集合一定存在一个圆和点的匹配方式使得每个圆匹配的点是按照xxx排序后的一段。
证明
考虑排序后的一段点如果一个圆覆盖了左边和右边的点而中间的点没有覆盖
类似于这样 红色的是点
因为下面的点保留下来了所以一定有一个圆覆盖它 假设这个圆在当前圆的圆心的左边在右边同理 看上去它覆盖了左边的点所以接下来我们的证明就往这个方向努力
注意到两个圆的半径都是RRR,所以两个圆交点所在的直线是两个圆心的中垂线
而两个圆心都在直线上方所以连线的中点也在直线上方所以中垂线一定和圆有一个直线上的交点这个可以用反证法证明。
这样根据意识流右边的圆 左边的部分一定被左边的圆覆盖了
如果圆半径不相同就会出现这样的情况 然后是一个很憨的dp
设dp(i,j,k)dp(i,j,k)dp(i,j,k)表示当前处理到排完序后的第iii个点上面的圆上次处理的是第jjj个下面是第kkk个(因为上面的结论只对一边有效所以两边要分别处理)
转移的时候是如果当前点在上/下面的圆内
可能上一个点也用了这个圆这个点接在后面可能上一个点用的是其他圆
注意圆不用排序因为第二、三个参数的含义是上次处理“了”这个圆这次可能会接着处理来找到最优解而不是处理“到”这个圆所以圆的坐标会反复横跳。
dp过程中实际上有很多方案并不满足每个圆对应一段因为没有也没法判断这个圆是否用过但这些方案一定不是最优解因为同一个圆被算了多次代价但实际上即使我们去重之后也可以达到相同的效果同时满足限制的都被统计入答案了所以可以找到最优解。
复杂度O(n4)O(n^4)O(n4)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 105
using namespace std;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) f(c-? -1:1),cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
typedef long long ll;
const int INF0x3f3f3f3f;
int R;
struct point{int x,y,c;}s[MAXN],w[MAXN],up[MAXN],low[MAXN];
inline bool check(const point a,const point b){return (ll)(a.x-b.x)*(a.x-b.x)(ll)(a.y-b.y)*(a.y-b.y)(ll)R*R;}
inline bool operator (const point a,const point b){return a.xb.x? a.yb.y:a.xb.x;}
int cnt1,cnt2;
int dp[MAXN][MAXN][MAXN];
int main()
{int n,m;nread(),mread(),Rread();for (int i1;in;i) s[i].xread(),s[i].yread();for (int i1;im;i) w[i].xread(),w[i].yread(),w[i].cread();int tot0;for (int i1;in;i)for (int j1;jm;j)if (check(s[i],w[j])){s[tot]s[i];break;}sort(s1,stot1);for (int i1;im;i)if (w[i].y0) low[cnt2]w[i];else up[cnt1]w[i];for (int i0;icnt1;i)for (int j0;jcnt2;j)dp[0][i][j]INF;dp[0][0][0]0;for (int k1;ktot;k)for (int i0;icnt1;i)for (int j0;jcnt2;j){dp[k][i][j]INF;if (icheck(up[i],s[k])) {dp[k][i][j]min(dp[k][i][j],dp[k-1][i][j]); for (int l0;lcnt1;l) dp[k][i][j]min(dp[k][i][j],dp[k-1][l][j]up[i].c);}if (jcheck(low[j],s[k])) {dp[k][i][j]min(dp[k][i][j],dp[k-1][i][j]); for (int l0;lcnt2;l) dp[k][i][j]min(dp[k][i][j],dp[k-1][i][l]low[j].c);}}int ansINF;for (int i0;icnt1;i)for (int j0;jcnt2;j)ansmin(ans,dp[tot][i][j]);printf(%d\n%d\n,tot,ans);return 0;
}
