数字三角形模型
1. 摘花生
就是最基础的数字三角形模型
状态表示 :
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示当前
(
i
,
j
)
(i,j)
(i,j)的最大价值
状态转移 :
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
?
1
]
[
j
]
,
f
[
i
]
[
j
?
1
]
)
f[i][j] = max(f[i-1][j],f[i][j-1])
f[i][j]=max(f[i?1][j],f[i][j?1])
2.最低通行费
这个题还是最基础的数字三角形模型
只是变向的问了
对于一个 N × N N×N N×N的网格,限定 2 N ? 1 2N-1 2N?1步走出去
根据曼哈顿距离,我们可以知道如果只往下和右走,那么所需的距离正好就是 2 N ? 1 2N-1 2N?1
因此问题又回到了那个模板的问题
3.方格取数
题意 :
对于方格
(
i
,
j
)
(i,j)
(i,j)都赋予一个
w
i
,
j
w_{i,j}
wi,j?
试问类似摘花生那种做法,做两次的最大值
拿完之后该点的权值为0
思路 :
如果分开走的话,那么第一次走完之后会有后效性影响第二次拿的价值,所以必须同时走
状态表示 :
f
[
i
1
]
[
j
1
]
[
i
2
]
[
j
2
]
f[i_1][j_1][i_2][j_2]
f[i1?][j1?][i2?][j2?]表示同时分别走到
从
(
1
,
1
)
开
始
走
到
(
i
1
,
j
1
)
(
i
2
,
j
2
)
从(1,1)开始走到(i_1,j_1)(i_2,j_2)
从(1,1)开始走到(i1?,j1?)(i2?,j2?)的路径的集合
状态计算 :
f
[
i
1
]
[
j
1
]
[
i
2
]
[
j
2
]
=
m
a
x
(
f[i_1][j_1][i_2][j_2]=max(
f[i1?][j1?][i2?][j2?]=max(
f
[
i
1
?
1
]
[
j
1
]
[
i
2
?
1
]
[
j
2
]
?
从
上
面
转
移
f[i_1-1][j_1][i_2-1][j_2] -从上面转移
f[i1??1][j1?][i2??1][j2?]?从上面转移
f
[
i
1
]
[
j
1
?
1
]
[
i
2
?
1
]
[
j
2
]
?
从
左
边
和
上
面
转
移
f[i_1][j_1-1][i_2-1][j_2] -从左边和上面转移
f[i1?][j1??1][i2??1][j2?]?从左边和上面转移
f
[
i
1
]
[
j
1
?
1
]
[
i
2
]
[
j
2
?
1
]
?
从
左
边
转
移
f[i_1][j_1-1][i_2][j_2-1] -从左边转移
f[i1?][j1??1][i2?][j2??1]?从左边转移
f
[
i
1
?
1
]
[
j
1
]
[
i
2
]
[
j
1
?
1
]
?
从
上
面
和
左
边
转
移
)
f[i_1-1][j_1][i_2][j_1-1] - 从上面和左边转移)
f[i1??1][j1?][i2?][j1??1]?从上面和左边转移)
当然因为拿完就置 0 0 0的存在,我们需要考虑 ( i 1 , j 1 ) ( i 2 , j 2 ) (i_1,j_1)(i_2,j_2) (i1?,j1?)(i2?,j2?)是否是相同的格子
因此我们可以做一个优化
我们令 k = i 1 + j 1 = i 2 + j 2 k=i_1+j_1=i_2+j_2 k=i1?+j1?=i2?+j2?
我们只需要 n ? 2 n*2 n?2的枚举 k k k以及枚举 i 1 i_1 i1?, i 2 i_2 i2?然后通过计算出来 j 1 j_1 j1? j 2 j_2 j2?即可
最后判断是否相同
const int N = 15;
int n;
int w[N][N], f[N*2][N][N];
int main() {
cin >> n;
int a,b,c;
while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
for(int k = 2; k <= 2*n; k++) {
for(int i1 = 1; i1 <= n; i1++) {
for(int i2 = 1; i2 <= n; i2++) {
int j1 = k-i1, j2 = k-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n) {
// 不能越界
int &x = f[k][i1][i2];
int t = w[i1][j1];
if(i1!=i2) t += w[i2][j2];
//不重合则需要加两个权重.
x = max(x, f[k-1][i1-1][i2-1]+t);
x = max(x, f[k-1][i1-1][i2]+t);
x = max(x, f[k-1][i1][i2-1]+t);
x = max(x, f[k-1][i1][i2]+t);
//保留最大属性
}
}
}
}
cout << f[n*2][n][n] << endl;
4.传纸条
这里和前面的方格取数不一样的是
方格取数是从同一个起点开始,但是这里是从两个对角开始
并且走过的点不能再回走
思路 :
证明出来,最优的路径显然不是两个相交路径之和,同时又因为从右下角回传可用对称等效为从左上角传
所以完全可用套用方格取数模板
