?時間限制: 1 s

?空間限制: 128000 KB

?題目等級 : 鉆石 Diamond

題解 題目描述?Description

菜菜看到了一個游戲，叫做方格游戲~

游戲規(guī)則是這樣的：

在一個n*n的格子中，在每個1*1的格子里都能獲得一定數(shù)量的積分獎勵，記左上角為(1,1)，右下角為(n,n)。游戲者需要選擇一條(1,1)到(n,n)的路徑，并獲得路徑上獎勵的積分。對于路徑當然也有要求啦，要求是只能往坐標變大的方向走【從(x,y)到(x+1,y)或者(x,y+1)】，走過2n-1個區(qū)域到達(n,n)。當然，獲得的積分最高的就能取勝啦。

這時，菜菜看到了他的好友月月，于是邀請她來玩雙人版的。雙人版的規(guī)則就是在單人版的基礎上加上一條兩人的路線不能相同。月月知道菜菜的很聰明，怕輸?shù)锰珣K，就不太愿意和他玩。菜菜可慌了，于是定義了一個公平值D，這個公平值等于倆人所選擇的路徑所能獲得的積分一一對應相減的差的絕對值之和，即D=sigma (|kxi-kyi|)|(kx，ky分別為菜菜，月月走過的每一個區(qū)域的叢林系數(shù)）。不過這可是個龐大的計算任務，菜菜找到了你，請你幫忙計算公平值的最大值。

輸入描述?Input Description

? ? 第一行，一個正整數(shù)n

????接下來的n行，每行n個整數(shù)，表示叢林中每個區(qū)域的公平值

輸出描述?Output Description

一個整數(shù)Dmax，即公平值的最大值

樣例輸入?Sample Input

4

1?2?3?4

1?5?3?2

8?1?3?4

3?2?1?5

樣例輸出?Sample Output

13

數(shù)據(jù)范圍及提示?Data Size & Hint

對于20%的數(shù)據(jù)，保證0＜n≤20

對于50%的數(shù)據(jù)，保證0＜n≤50

對于100%的數(shù)據(jù)，保證0＜n≤100且對于所有的i，j保證|Kij|≤300

分類標簽?Tags?點此展開?

動態(tài)規(guī)劃?棋盤型DP

代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,a[200][200],dp[200][200][400]; int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}} for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=2*n;k++)dp[i][j][k]=-2147483640;dp[1][1][2]=0; for(int k=3;k<=2*n;k++){for(int j=1;j<=n;j++){for(int i=1;i<=n;i++){if(k-i>n || k-j>n) continue;if(k-i<1 || k-j<1) break; else dp[i][j][k]=max(max(dp[i-1][j][k-1],dp[i][j][k-1]),max(dp[i][j-1][k-1],dp[i-1][j-1][k-1]))+abs(a[i][k-i]-a[j][k-j]);}}}cout<<dp[n][n][2*n]; }

?

?

思路： ?

? ?狀態(tài)壓縮，四維會爆！改成三維！?

? ?本題是一道典型的動態(tài)規(guī)劃題。

????我們首先來設計狀態(tài)，用f[i][j][k]表示第i步時，菜菜的路徑在橫坐標為j的區(qū)域，月月的路徑在橫坐標為k的格子上時，當前公平值的最大值。這樣三個值用來表示狀態(tài)已經(jīng)足夠，因為菜菜和月月的位置可以用(j,i-j+1)和(k,i-k+1)來表示。

????狀態(tài)轉移方程根據(jù)兩人移動的方法設置如下：

????f[i][j][k]?=?max{f[i-1][j-x][k-y]}?+?|a[j][i-j+1]?-?a[k][i-k+1]|,??x,y?=?0,1}

????這樣，本題就解決了，本題的時間復雜度為O(n3)。?

千萬要注意在循環(huán)的時候是先循環(huán)k再循環(huán)j最后i ?也就是說要倒著循環(huán)

轉載于:https://www.cnblogs.com/z360/p/6746300.html

總結

以上是生活随笔為你收集整理的codevs——2853 方格游戏（棋盘DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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