AGC004E - Salvage Robots

Solution

怎么又雙叒叕遇到和$NOIP2020T4$和那道$CF$題一樣的題了啊，慘痛回憶$QAQ$。

大概就是把問題看成剛開始的點不動，整個網(wǎng)格圖動，機器人向上$1$格等于網(wǎng)格整體向下$1$格，左右同理。如果網(wǎng)格某一時刻有一部分在邊界外面，就把那些部分切掉，然后把所有經(jīng)過原點（$E$所在的點）的機器人都收集起來。

因此倘若我們向上、下、左、右分別移動了最多$u,d,l,r$格，那么現(xiàn)在的網(wǎng)格就是$[d+1...n?u,r+1...m?l]$范圍內(nèi)的，然后我們可以選擇一個邊界位置擴展出去，假設(shè)$u+1$，那么假設(shè)移動到了位置$(u+1,y),y\in [l,r]$，顯然對于所有$y\in [max(r+1,l),min(m?l,r)]$,位置$(u+1,y)$上的機器人都可以被收集而不影響邊界大小。這里要對邊界取$max/min$是因為邊界外的機器人都超出過邊界消失了。

于是我們有了一個$dp$的思路：令$f_{u,d,l,r}$表示向上、下、左、右分別移動了最多$u,d,l,r$格最多收集的機器人。

每次可以從邊界往外擴展一格，然后把那個邊界上的機器人都加到新的狀態(tài)里。預(yù)處理橫縱方向的機器人個數(shù)前綴和即可$O(1)$轉(zhuǎn)移。

時間復(fù)雜度$O(n^4)$，空間也是$O(n^4)$，空間$256MB$，只能開$short$。

Code

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const int MAXN=101; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int X,Y; char st[MAXN]; short f[MAXN][MAXN][MAXN][MAXN],sl[MAXN][MAXN],su[MAXN][MAXN]; signed main() {int n=read(),m=read();for (int i=1;i<=n;i++){scanf("%s",st+1);for (int j=1;j<=m;j++) {if (st[j]=='E') X=i,Y=j;if (st[j]=='o') sl[i][j]=su[i][j]=1;}}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++) sl[i][j]+=sl[i][j-1],su[i][j]+=su[i-1][j];for (int u=0;u<X;u++)for (int d=0;d<=n-X;d++)for (int l=0;l<Y;l++)for (int r=0;r<=m-Y;r++) f[u][d][l][r]=-n*m;f[0][0][0][0]=0;short mx=0;for (int u=0;u<X;u++)for (int d=0;d<=n-X;d++)for (int l=0;l<Y;l++)for (int r=0;r<=m-Y;r++){if (X-(u+1)>=d+1) upmax(f[u+1][d][l][r],(short)(f[u][d][l][r]+sl[X-(u+1)][min(Y+r,m-l)]-sl[X-(u+1)][max(Y-l-1,r)]));if (X+(d+1)<=n-u) upmax(f[u][d+1][l][r],(short)(f[u][d][l][r]+sl[X+(d+1)][min(Y+r,m-l)]-sl[X+(d+1)][max(Y-l-1,r)]));if (Y-(l+1)>=r+1) upmax(f[u][d][l+1][r],(short)(f[u][d][l][r]+su[min(X+d,n-u)][Y-(l+1)]-su[max(X-u-1,d)][Y-(l+1)]));if (Y+(r+1)<=m-l) upmax(f[u][d][l][r+1],(short)(f[u][d][l][r]+su[min(X+d,n-u)][Y+(r+1)]-su[max(X-u-1,d)][Y+(r+1)]));upmax(mx,f[u][d][l][r]);}printf("%d\n",(int)mx);return 0; }

總結(jié)

以上是生活随笔為你收集整理的AGC004E - Salvage Robots(dp，思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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