獎學金
抱歉，題目表述有誤，導致一些同學讀錯題目了，但是審核又通過了就改不了題目內容了，
抱歉抱歉！
輸入的內容應該是接下來 1 ? n 1 - n 1?n行 ，每行有 1 到 m 個 數 1到m個數 1到m個數
常規解法1：動態規劃
時間復雜度
O
(
N
4
)
O(N^4)
O(N4)
一個人時
對于單人,一個經典的題目：走方格
我們知道的DP做法，
f
(
i
,
j
)
=
m
a
x
{
f
(
i
,
j
?
1
)
,
f
(
i
?
1
,
j
)
}
+
a
[
i
]
[
j
]
f(i,j)=max\{f(i,j-1),f(i-1,j)\}+a[i][j]
f(i,j)=max{f(i,j?1),f(i?1,j)}+a[i][j]
兩個人時
那么對于兩個人的情況，我們可以加多兩個維度，表示另外一個人的走路情況
f
(
i
,
j
,
k
,
l
)
f(i,j,k,l)
f(i,j,k,l) 然后列舉每個人的走路情況,類似第一種做法
f
[
i
]
[
j
]
[
k
]
[
l
]
=
m
a
x
(
f
[
i
]
[
j
?
1
]
[
k
]
[
l
?
1
]
,
f
[
i
]
[
j
?
1
]
[
k
?
1
]
[
l
]
,
f
[
i
?
1
]
[
j
]
[
k
?
1
]
[
l
]
,
f
[
i
?
1
]
[
j
]
[
k
]
[
l
?
1
]
)
+
a
[
i
]
[
j
]
+
a
[
k
]
[
l
]
;
f[i][j][k][l] = max(f[i][j-1][k][l-1],f[i][j-1][k-1][l],f[i-1][j][k-1][l],f[i-1][j][k][l-1])+a[i][j]+a[k][l];
f[i][j][k][l]=max(f[i][j?1][k][l?1],f[i][j?1][k?1][l],f[i?1][j][k?1][l],f[i?1][j][k][l?1])+a[i][j]+a[k][l];
但是空間，時間復雜度可以優化
定義
f
(
p
,
i
,
j
)
f(p,i,j)
f(p,i,j)表示當前走了
p
p
p步，第一個人走到第
i
i
i行，第二個人走到第j行的最大價值，
顯然兩個人的坐標都可以計算出來，第一個人是 ( i , p ? i + 1 ) (i,p-i+1) (i,p?i+1)，第二個人是 ( j , p ? j + 1 ) (j,p-j+1) (j,p?j+1)，
轉移就考慮兩個人的上一步是怎樣走的，
f
[
p
]
[
i
]
[
j
]
=
m
a
x
(
m
a
x
(
f
[
p
?
1
]
[
i
]
[
j
]
,
f
[
p
?
1
]
[
i
?
1
]
[
j
]
)
,
m
a
x
(
f
[
p
?
1
]
[
i
]
[
j
?
1
]
,
f
[
p
?
1
]
[
i
?
1
]
[
j
?
1
]
)
)
+
a
[
i
]
[
p
?
i
+
1
]
+
a
[
j
]
[
p
?
j
+
1
]
f[p][i][j] = max(max(f[p - 1][i][j], f[p - 1][i - 1][j]), max(f[p - 1][i][j - 1], f[p - 1][i - 1][j - 1])) + a[i][p - i + 1] + a[j][p - j + 1]
f[p][i][j]=max(max(f[p?1][i][j],f[p?1][i?1][j]),max(f[p?1][i][j?1],f[p?1][i?1][j?1]))+a[i][p?i+1]+a[j][p?j+1]
三個人時
f
(
i
,
j
,
k
,
u
)
f(i,j,k,u)
f(i,j,k,u)表示第
i
i
i步時，三個人所在的行數分別為
j
，
k
，
u
j，k，u
j，k，u
三個人的坐標為
(
j
,
j
?
i
+
1
)
,
(
k
,
k
?
i
+
1
)
,
(
u
,
u
?
i
+
1
)
(j, j - i + 1), (k, k - i + 1),(u, u - i + 1)
(j,j?i+1),(k,k?i+1),(u,u?i+1)
從左邊或者下邊走來，
2
×
2
×
2
2\times 2\times 2
2×2×2，一共8種可能，類似上面的情況，具體見代碼
code:
#include<bits/stdc++.h>
using namespace std;
const int N = 125, M = 65;
int f[N][M][M][M], g[M][M], n, m;
int main() {
cin >> n >> m;
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
int i = 1, j = n;
for (int i = 1; i <= n + m; i++) {
for (int j = 1; j <= n && j <= i; j++) {
for (int k = 1; k <= n && k <= i; k++) {
for (int u = 1; u <= n && u <= i; u++) {
int w = g[j][i - j + 1];
if (k != j) w += g[k][i - k + 1];
if (u != k && j != u) w += g[u][i - u + 1];
int maxv = 0;
maxv = max(f[i - 1][j][k - 1][u], maxv);
maxv = max(f[i - 1][j][k][u - 1], maxv);
maxv = max(f[i - 1][j - 1][k][u], maxv);
maxv = max(f[i - 1][j - 1][k - 1][u], maxv);
maxv = max(f[i - 1][j - 1][k][u - 1], maxv);
maxv = max(f[i - 1][j][k - 1][u - 1], maxv);
maxv = max(f[i - 1][j - 1][k - 1][u - 1], maxv);
maxv = max(f[i - 1][j][k][u], maxv);
f[i][j][k][u] = max(f[i][j][k][u], maxv + w);
}
}
}
}
cout << f[n + m][n][n][n] << endl;
return 0;
}
騷操作：圖論建模（網路流）
但是我們發現這個題目如果拓展成k個人的情況那該怎么辦啊，用動態規劃的話,狀態又很繁瑣和空間不太夠，時間直接上升到
O
(
n
k
)
O(n^k)
O(nk)了
這個時候就需要一點圖論的功底了，接下來我們將如何用
M
2
l
o
g
N
M^2logN
M2logN解決此類問題的，
前置知識
- 網路流（最大流）基礎入門
- 費用流
如何將這個題目轉化為一個網路流題目呢
對于一個格子我們只能取一個數對吧，也就是說取完了就不能再取了，但是隊友還得路過那里啊，怎么辦呢？
我們將格子拆分成兩個，具體來說就是將改點分裂成兩個，一個是開始取得點（入點），一個是去后的點（出點），將該點的權值變為連邊費用，因為只能一個人取啊，所以我們將該入點與出點之間的之間額的流量改為
1
1
1
那該格子走到另外一個格子呢，我們可以將該點的出點與另外一個入點連邊，費用為
0
0
0，流量為無窮（因為可以重復走，代價為0），源點與第一個點連代價為
0
0
0的，流量為
k
k
k的邊,匯點與第一個點連代價為
0
0
0的，流量為
k
k
k的邊.
跑一下最大費用最大流即可啦，
對于網路流模板不難，建模難！
建模后類似此圖（圖畫得很丑，不完整，見諒，主要表達思想）
跑一下網路最大費用最大流即可
code:
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+100;
int head[N],ver[N],nex[N],edge[N],cost[N];
int tot=1;
void addedge(int x,int y,int z,int c){
ver[++tot]=y,nex[tot]=head[x],cost[tot]=c;
edge[tot]=z,head[x]=tot;
}
void add(int x,int y,int z,int c){
addedge(x,y,z,c);
addedge(y,x,0,-c);
}
//以下費用流基操，不介紹
int maxflow=0,maxcost=0;
int n,m,s,t;
int d[N];
int in[N];
int incf[N];
int pre[N];
bool spfa(){
queue<int> q;
memset(d,0xef,sizeof(d));
memset(in,0,sizeof(0));
q.push(s);
d[s]=0,in[s]=1;
incf[s]=INF;
while(!q.empty()){
int x=q.front();q.pop();
in[x]=0;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(!edge[i]) continue;
if(d[y]<d[x]+cost[i]){
d[y]=d[x]+cost[i];
incf[y]=min(incf[x],edge[i]);
pre[y]=i;
if(!in[y]) q.push(y),in[y]=1;
}
}
}
if(d[t]==0xefefefef) return 0;
return 1;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i]-=incf[t];
edge[i^1]+=incf[t];
x=ver[i^1];
}
maxflow+=incf[t];
maxcost+=incf[t]*d[t];
}
int num(int i,int j){
return (i-1)*m+j;
}
int main(){
int k=3; //三個人的情況
cin>>n>>m;
s=3*n*m;t=s+1; //源點，匯點
int p=n*m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
add(num(i,j),num(i,j)+p,1,x);
add(num(i,j),num(i,j)+p,INF,0);
if(i+1<=n) add(num(i,j)+p,num(i+1,j),INF,0);
if(j+1<=m) add(num(i,j)+p,num(i,j+1),INF,0);
}
}
add(s,num(1,1),k,0);
add(num(n,m)+p,t,k,0);
while(spfa()) update();
cout<<maxcost<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198767.html
標籤：其他
上一篇：約瑟夫環
下一篇：DFS 深度優化搜索