【試題描述】
小FF的第一片礦區(qū)已經(jīng)開始運作了， 他著手開展第二片礦區(qū)……
小FF的第二片礦區(qū)， 也是”NewBe_One“計劃的核心部分， 因為在這片礦區(qū)里面有全宇宙最稀有的兩種礦物，科學家稱其為NEW礦和BE礦。
礦區(qū)是被劃分成一個n*m的矩形區(qū)域。 小FF探明了每一小塊區(qū)域里的NEW礦和BE礦的蘊藏量， 并且小FF還在礦區(qū)的北邊和西邊分別設置了NEW礦和BE礦的收集站。你的任務是設計一個管道運輸系統(tǒng)，使得運送的NEW礦和BE礦的總量最多。
管道的型號有兩種，一種是東西向，一種是南北向。在一個格子內(nèi)你能建造一種管道，但丌能兩種都建。如果兩個同類型管道首位相接，它們就可以被連接起來。
另外這些礦物都十分丌穩(wěn)定，因此它們在運送過程中都丌能拐彎。這就意味著如果某個格子上建有南北向管道，但是它北邊的格子建有東西向管道，那么這根南北向管道內(nèi)運送的任何東西都將丟失。迚一步地，運到NEW礦收集站的BE礦也會丟失，運到BE礦收集站的NEW礦也會丟失。
【輸入格式】
第一行包含兩個整數(shù)n和m，表示礦區(qū)大小。
以下n行，每行m個整數(shù)，其中第i行第j個整數(shù)G[ i , j ] 描述各個格子上的BE礦數(shù)量。接下來以類似的矩陣表示各個格子上的NEW礦數(shù)量。
【輸出格式】
僅一個整數(shù)， 表示最多可以采集到的NEW礦和BE礦的總量。
【輸入樣例】
4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
【輸出樣例】
98
【數(shù)據(jù)范圍】
對于30%的數(shù)據(jù)： 0<= n，m <=100;
對于100%的數(shù)據(jù)： 0<= n, m <=1000;
0<= G[ i, j ] <=1000.
【分析】
每個點只有兩種狀態(tài)，放be的管道或者放new的管道。
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 1010
4: using namespace std;
5:
6: int g[maxn][maxn][2];
7: long long f[maxn][maxn][2];
8: int ne[maxn][maxn],be[maxn][maxn];
9: int n,m;
10:
11: int main()
12: {
13: freopen("industry.in","r",stdin);
14: freopen("industry.out","w",stdout);
15:
16: scanf("%d%d",&n,&m);
17: for (int i=1;i<=n;++i)
18: for (int j=1;j<=m;++j)
19: scanf("%d",&g[i][j][0]);
20: for (int i=1;i<=n;++i)
21: for (int j=1;j<=m;++j)
22: scanf("%d",&g[i][j][1]);
23: for (int i=1;i<=n;++i)
24: for (int j=1;j<=m;++j)
25: {
26: ne[i][j]=ne[i-1][j]+g[i][j][1];
27: be[i][j]=be[i][j-1]+g[i][j][0];
28: }
29: for (int i=1;i<=n;++i)
30: for (int j=1;j<=m;++j)
31: {
32: f[i][j][0]=be[i][j]+max(f[i-1][j][0],f[i-1][j][1]);
33: f[i][j][1]=ne[i][j]+max(f[i][j-1][1],f[i][j-1][0]);
34: }
35: printf("%lld\n",max(f[n][m][1],f[n][m][0]));
36: return 0;
37: }
38: