CF1253E Antenna Coverage

題意：

現(xiàn)在有n個(gè)點(diǎn)，每個(gè)點(diǎn)的坐標(biāo)為xi，以及一個(gè)范圍值si，可以覆蓋左右范圍[xi-si,xi+si]
每次操作，可以花費(fèi)代價(jià)1讓第i個(gè)天線的si增加1，每個(gè)天線都可以進(jìn)行多次操作。現(xiàn)在請(qǐng)問(wèn)你最少需要花費(fèi)多少代碼，使得[1,m]內(nèi)每個(gè)位置都被至少一個(gè)天線覆蓋

題解：

參考題解
很奇妙的思路
我們?cè)O(shè)f[i]表示[1,i]被全部覆蓋的最小花費(fèi)，答案為$f_m$
首先引入一個(gè)新的點(diǎn)，坐標(biāo)為0，這樣f的初始值就是f[i]=i
這個(gè)點(diǎn)很重要，其保證了$f_{i+1}<=f_i+1$，f是單調(diào)上升的，且該點(diǎn)的引入并未影響答案，因?yàn)槲覀冏詈蟮拇鸢甘莊[n]，而在最左側(cè)加入一個(gè)點(diǎn)，f[n]=n相當(dāng)于是最差情況，所以不會(huì)影響答案
然后我們可以進(jìn)行轉(zhuǎn)移：
對(duì)于點(diǎn)i，我們找在i前面的區(qū)間[l,r]，（r要小于i），此時(shí)r要擴(kuò)展x=i-r[]才能覆蓋i，l也要擴(kuò)展x，那么i就可以通過(guò)坐標(biāo)j-1=l-x-1來(lái)更新
如圖

正確性證明可以看參考題解

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=100; struct node{int x,s; }a[maxn]; int f[200004]; int l[maxn]; int r[maxn]; int main() { // rd_test();int n,m;read(n,m);for(int i=1;i<=n;i++){read(a[i].x,a[i].s);l[i]=a[i].x-a[i].s; r[i]=a[i].x+a[i].s;}for(int i=1;i<=m;i++)f[i]=i;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(l[j]<=i&&i<=r[j]){f[i]=f[i-1];break;}if(r[j]<i){int x=i-r[j];f[i]=min(f[max(0,l[j]-x-1)]+x,f[i]);}}}cout<<f[m];//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的CF1253E Antenna Coverage的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。