關(guān)于 P1004 的題解

幾個月沒有來博客寫題解 找借口不寫題 了，40多道題已經(jīng)腐爛在U盤中。

o(￣▽￣)ブ

一開始看到題目，我的心情是苦悶mengbi的，我太弱啦，不還這種題的！

但si，這帥氣的題目范圍終究奠定了這道題水題的地位。

終于，我靠著不懈的毅力，以及強大的dalao題解團 得以AC了這道題，爽！！！

下面看看蒟蒻是如何連抄帶做出這道題的吧？

(￢︿??￢☆)

(￣_,￣ )

壹.

模擬方式~~

很好理解，假設(shè)有兩個小人從起點一起走，至于在那里走，很好想的嗎：

---

scanf("%d",&n);while(x>0&&y>0&&v>0){scanf("%d%d%d",&x,&y,&v);map[x][y]=v;}

嗯~ o(￣▽￣)o，這個，好像 map 不可以用

氟鈾碳鉀

待會兒用 mmp

---

貳.

開始走。

兩人位置分別為(i,j)，(k,l) 。

兩人的位置遞推式應(yīng)為：

---

f[i][j][k][l]= max( f[i-1][j][k-1][l], f[i][j-1][k][l-1], f[i][j-1][k-1][l], f[i-1][j][k][l-1]) +mmp[i][j]+mmp[k][l];

~~p.s:十分溫馨的提示：沒有草稿紙的去死呦(*^_^*)~~

---

叁.

兩個人碰到一起開始吵架怎么辦？

到一起算了兩次怎么辦？

一位 dalao yjxyjx 說：““既然加了兩遍，那就減去一遍啊”——樓下大佬&icydalao”。

說的好。

獻上完整的代碼：

---

#include<bits/stdc++.h>using namespace std;int n; int x=1,y=1,v=1; int mmp[15][15]; int f[15][15][15][15]; int mex(int a,int b,int c,int d) {if(b>a)a=b;if(c>a)a=c;if(d>a)a=d;return a; } int main() {scanf("%d",&n);while(x>0&&y>0&&v>0){scanf("%d%d%d",&x,&y,&v);mmp[x][y]=v;}for(register int i=1;i<=n;i++){for(register int j=1;j<=n;j++){for(register int k=1;k<=n;k++){for(register int l=1;l<=n;l++){f[i][j][k][l]=mex(f[i-1][j][k-1][l],f[i][j-1][k][l-1],f[i][j-1][k-1][l],f[i-1][j][k][l-1])+mmp[i][j]+mmp[k][l];if((i==k)&&(j==l)){f[i][j][k][l]-=(mmp[i][j]);}}}}}printf("%d",f[n][n][n][n]);return 0; }

關(guān)于 mex ，你懂的(￣▽￣)"~~~

---

就這樣，謝謝！！！

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

總結(jié)

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

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