傳送門

題意：一個$x\in (?\infty ,+\infty ),y\in [0,R]$的矩形中有$n$個點，矩形外有$m$個半徑均為$R$的圓，有獨立的代價$c_i$。求覆蓋最多的點所需的最小代價。

$n,m\le 100$

顯然先把永遠不可能覆蓋到的點扔掉，然后轉化為覆蓋所有點

先考慮圓心都在矩形上方的情況

結論 對于一個合法（即覆蓋所有點）的圓的集合，一定存在一個圓和點的匹配方式，使得每個圓匹配的點是按照$x$排序后的一段。

證明

考慮排序后的一段點，如果一個圓覆蓋了左邊和右邊的點，而中間的點沒有覆蓋

類似于這樣：

（紅色的是點）

因為下面的點保留下來了，所以一定有一個圓覆蓋它 假設這個圓在當前圓的圓心的左邊，在右邊同理

看上去它覆蓋了左邊的點，所以接下來我們的證明就往這個方向努力

注意到兩個圓的半徑都是$R$,所以兩個圓交點所在的直線是兩個圓心的中垂線

而兩個圓心都在直線上方，所以連線的中點也在直線上方，所以中垂線一定和圓有一個直線上的交點，這個可以用反證法證明。

這樣根據意識流，右邊的圓 左邊的部分一定被左邊的圓覆蓋了

如果圓半徑不相同，就會出現這樣的情況：

然后是一個很憨的dp

設$dp(i,j,k)$表示當前處理到排完序后的第$i$個點，上面的圓上次處理的是第$j$個，下面是第$k$個(因為上面的結論只對一邊有效，所以兩邊要分別處理)

轉移的時候是如果當前點在上/下面的圓內

可能上一個點也用了這個圓，這個點接在后面

可能上一個點用的是其他圓

注意圓不用排序，因為第二、三個參數的含義是上次處理“了”這個圓，這次可能會接著處理來找到最優解，而不是處理“到”這個圓，所以圓的坐標會反復橫跳。

dp過程中實際上有很多方案并不滿足每個圓對應一段（因為沒有也沒法判斷這個圓是否用過），但這些方案一定不是最優解（因為同一個圓被算了多次代價，但實際上即使我們去重之后也可以達到相同的效果），同時滿足限制的都被統計入答案了，所以可以找到最優解。

復雜度$O(n^4)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #define MAXN 105 using namespace std; inline int read() {int ans=0,f=1;char c=getchar();while (!isdigit(c)) f=(c=='-'? -1:1),c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return f*ans; } typedef long long ll; const int INF=0x3f3f3f3f; 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.x==b.x? a.y<b.y:a.x<b.x;} int cnt1,cnt2; int dp[MAXN][MAXN][MAXN]; int main() {int n,m;n=read(),m=read(),R=read();for (int i=1;i<=n;i++) s[i].x=read(),s[i].y=read();for (int i=1;i<=m;i++) w[i].x=read(),w[i].y=read(),w[i].c=read();int tot=0;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (check(s[i],w[j])){s[++tot]=s[i];break;}sort(s+1,s+tot+1);for (int i=1;i<=m;i++)if (w[i].y<0) low[++cnt2]=w[i];else up[++cnt1]=w[i];for (int i=0;i<=cnt1;i++)for (int j=0;j<=cnt2;j++)dp[0][i][j]=INF;dp[0][0][0]=0;for (int k=1;k<=tot;k++)for (int i=0;i<=cnt1;i++)for (int j=0;j<=cnt2;j++){dp[k][i][j]=INF;if (i&&check(up[i],s[k])) {dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][j]); for (int l=0;l<=cnt1;l++) dp[k][i][j]=min(dp[k][i][j],dp[k-1][l][j]+up[i].c);}if (j&&check(low[j],s[k])) {dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][j]); for (int l=0;l<=cnt2;l++) dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][l]+low[j].c);}}int ans=INF;for (int i=0;i<=cnt1;i++)for (int j=0;j<=cnt2;j++)ans=min(ans,dp[tot][i][j]);printf("%d\n%d\n",tot,ans);return 0; }

總結

以上是生活随笔為你收集整理的【ZJOI2015】幻想乡 Wi-Fi 搭建计划【几何】【贪心】【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。