傳送門

Description

給你一個(gè)\(n~\times~m\)的矩陣，一開始你在第\(r\)行第\(c\)列。你的上下移動不受限制，向左最多移動\(x\)次，向右最多移動\(y\)次。求你最多能到多少個(gè)點(diǎn)。包括起始點(diǎn)。

Input

第一行是\(n\)和\(m\)，代表矩陣規(guī)模。

第二行是\(r\)和\(c\)，代表你的位置

第三行是\(x\)和\(y\)，代表移動限制

下面\(n\)行每行\(m\)個(gè)字符，有且僅有'.'和''兩種。如果第\(i\)行第\(j\)列是''代表你不能經(jīng)過這個(gè)點(diǎn)。

Output

輸出一行一個(gè)數(shù)代表能到的最多點(diǎn)數(shù)

Sample Input

4 5 3 2 1 2 ..... .***. ...** *....

Sample Output

10

Hint

\(For~All:\)

\(0~\leq~n,m,r,c~\leq~2000\),\(0~\leq~x,y~\leq~10^9\)

Solution

樸素的\(bfs\)顯然是對的，可以狀態(tài)太多存不下。

考慮如果從\((sx,sy)\)點(diǎn)到一個(gè)點(diǎn)\((x,y)\)時(shí)，假設(shè)共向右走了\(r\)步，向左走了\(l\)步，顯然\(r-l\)是一個(gè)定值。具體的，\(r-l~=~y-sy\)。于是，對于任意一個(gè)目標(biāo)\((x,y)\)，發(fā)現(xiàn)\(l\)事實(shí)上與\(r\)線性正相關(guān)。對于一個(gè)點(diǎn)，顯然到該點(diǎn)的\(r\)越小越好，同時(shí)由于\(l\)和\(r\)線性正相關(guān)，所以最小化\(r\)的同時(shí)，\(l\)已經(jīng)被最小化了。于是可以直接建圖跑最短路，所有向右的邊權(quán)為1，其他邊權(quán)為0。跑完后掃描整個(gè)地圖就可以判斷合法性了。

這里的一個(gè)新姿勢是\(0/1bfs\)。當(dāng)邊權(quán)只有\(0/1\)時(shí)，可以使用雙端隊(duì)列進(jìn)行bfs，具體的，當(dāng)當(dāng)前邊的權(quán)值時(shí)\(0\)時(shí)，將終點(diǎn)壓入隊(duì)首，否則壓入隊(duì)尾。考慮這么做的正確性：易證任意一時(shí)刻隊(duì)列中的點(diǎn)dist差值不超過1。于是正確性顯然。\(0/1bfs\)的復(fù)雜度為\(O(V+E)\)。相比dij少了一個(gè)log。

Code

#include<queue> #include<cstdio> #include<cstring> #define rg register #define ci const int #define cl const long long inttypedef long long int ll;namespace IO{char buf[110]; }template <typename T> inline void qr(T &x) {rg char ch=getchar(),lst=' ';while((ch > '9') || (ch < '0')) lst=ch,ch=getchar();while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(lst == '-') x=-x; }template <typename T> inline void qw(T x,const char aft,const bool pt) {if(x < 0) {putchar('-');x=-x;}rg int top=0;do {IO::buf[++top]=x%10+'0';} while(x/=10);while(top) putchar(IO::buf[top--]);if(pt) putchar(aft); }template <typename T> inline T mmax(const T a,const T b) {return a > b ? a : b;} template <typename T> inline T mmin(const T a,const T b) {return a < b ? a : b;} template <typename T> inline T mabs(const T a) {return a < 0 ? -a : a;}template <typename T> inline void mswap(T &a,T &b) {T _temp=a;a=b;b=_temp; }const int maxn = 2010;const int fx[]={0,-1,0,1}; const int fy[]={1,0,-1,0}; const int fv[]={1,0,0,0};int n,m,sx,sy,x,y; int MU[maxn][maxn]; char mp[maxn][maxn];std::deque<int>Qx,Qy;int main() {qr(n);qr(m);qr(sx);qr(sy);qr(x);qr(y);for(rg int i=1;i<=n;++i) scanf("%s",mp[i]+1);memset(MU,0x3f,sizeof MU);MU[sx][sy]=0; Qx.push_front(sx);Qy.push_front(sy);while(!Qx.empty()) {int hx=Qx.front(),hy=Qy.front();Qx.pop_front();Qy.pop_front();for(rg int i=0;i<4;++i) {int dx=hx+fx[i],dy=hy+fy[i];if((dx > n) || (dy > m) || (!dx) || (!dy) || (mp[dx][dy] == '*') || (MU[dx][dy] <= MU[hx][hy]+fv[i])) continue;MU[dx][dy]=MU[hx][hy]+fv[i];if(i) {Qx.push_front(dx);Qy.push_front(dy);}else {Qx.push_back(dx);Qy.push_back(dy);}}}rg int _ans=0;for(rg int i=1;i<=n;++i) {for(rg int j=1;j<=m;++j) if(mp[i][j] != '*') {if((MU[i][j] <= y) && ((MU[i][j]-j+sy) <= x)) ++_ans;}}qw(_ans,'\n',true);return 0; }

Summary

當(dāng)題設(shè)需要最小化多個(gè)變量時(shí)，不妨考慮變量間的相關(guān)關(guān)系，從此轉(zhuǎn)化成單變量的極值問題。

當(dāng)邊權(quán)只有\(0\)和\(1\)的時(shí)候，可以考慮使用\(0/1bfs\),省去dij的log。

轉(zhuǎn)載于:https://www.cnblogs.com/yifusuyi/p/9800308.html

總結(jié)

以上是生活随笔為你收集整理的【极值问题】【CF1063B】 Labyrinth的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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