題目鏈接

https://atcoder.jp/contests/agc004/tasks/agc004_e

題解

本題的難度不在于想到大體思路，而在于如何把代碼寫對(duì)。。
首先我們可以不讓機(jī)器人動(dòng)，讓出口和邊界一起動(dòng)。
然后設(shè)\(dp[l][r][u][d]\)表示出口往四個(gè)方向分別動(dòng)了最多\(l,r,u,d\)格，最大能圈住幾個(gè)機(jī)器人。
轉(zhuǎn)移以向下為例: 向下轉(zhuǎn)移合法的條件為\(x_0+d<n-u\) (\(x_0,y_0\)為起點(diǎn)坐標(biāo))，因?yàn)槌隹诘奈恢檬?span id="ze8trgl8bvbq" class="math inline">\(x_0+d+1\), 而同時(shí)要滿足點(diǎn)在網(wǎng)格上下邊界圈成的合法矩形內(nèi)，網(wǎng)格下邊界的最上位置為\(n-u\).
注意向下合法和向上合法并不等價(jià)，比如一種情況是起點(diǎn)離上邊界很近離下邊界很遠(yuǎn)，就有可能出現(xiàn)先上后下能完成但是先下后上完不成的情況。
防止MLE可以滾動(dòng)數(shù)組或者開short.

時(shí)間復(fù)雜度\(O(n^4)\).

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #include<cassert> #include<cstring> #include<algorithm> using namespace std;const int N = 100; short dp[N+3][N+3][N+3][N+3]; int s[N+3][N+3]; char a[N+3][N+3]; int n,m,sx,sy;int getsum(int lx,int rx,int ly,int ry) {return s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1];}int updmax(short &x,short y) {x = x>y?x:y;}int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) scanf("%s",a[i]+1);for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){s[i][j] = (a[i][j]=='o'?1:0)+s[i-1][j]+s[i][j-1]-s[i-1][j-1];if(a[i][j]=='E') {sx = i,sy = j;}}}memset(dp,213,sizeof(dp));dp[0][0][0][0] = 0; short ans = 0;for(int l=0; sy-l>0; l++){for(int r=0; sy+r<=m; r++){for(int u=0; sx-u>0; u++){for(int d=0; sx+d<=n; d++){updmax(ans,dp[l][r][u][d]);int ly = max(1+r,sy-l),ry = min(m-l,sy+r),lx = max(1+d,sx-u),rx = min(n-u,sx+d); // printf("l%d r%d u%d d%d x[%d,%d] y[%d,%d]\n",l,r,u,d,lx,rx,ly,ry);if(sx+d<n-u){updmax(dp[l][r][u][d+1],dp[l][r][u][d]+getsum(sx+d+1,sx+d+1,ly,ry));}if(sx-u>1+d){updmax(dp[l][r][u+1][d],dp[l][r][u][d]+getsum(sx-u-1,sx-u-1,ly,ry));}if(sy+r<m-l){updmax(dp[l][r+1][u][d],dp[l][r][u][d]+getsum(lx,rx,sy+r+1,sy+r+1));}if(sy-l>1+r){updmax(dp[l+1][r][u][d],dp[l][r][u][d]+getsum(lx,rx,sy-l-1,sy-l-1));}}}}}printf("%d\n",(int)ans);return 0; }

總結(jié)

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

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