1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1
:摘花生。
解题思路:DP。
状态定义
f[i][j]
:从(1,1)走到(i,j)所摘花生总和。
状态转移,有:
-
从上方走到(i,j),有
f[i-1][j] + w[i][j]
。
-
从左侧走到(i,j),有
f[i][j-1] + w[i][j]
。
C++代码如下,
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int w[N][N];
int f[N][N];
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> w[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j];
}
}
cout << f[n][m] << endl;
}
return 0;
}
题目2
:最低通行费用。N*N的网格,求最低通行费用。
解题思路:DP。
C++代码如下,
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int a[N][N];
int f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
memset(f, 0x3f, sizeof f);
f[1][1] = a[1][1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == 1 & j == 1) continue; //已经被初始化了,无需计算
f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];
}
}
cout << f[n][n] << endl;
return 0;
}
题目3
:方格取数。给定N*N的方格,每个方格中有一个数,从左上角走到右下角,有两个人A和B,方格中的数只能被取一次,求最大值。
解题思路:DP。
状态定义
f[k][i1][i2]
:横坐标和纵坐标之和为k,且A走到(i1,k-i1)处,B走到(i2,k-i2)处,该情况下路径之和的最大值。
f[k][i1][i2]
的状态转移,即是求下面4种情况的最大值,
-
A从上方走到(i1,k-i1),B从上方走到(i2,k-i2),即
f[k-1][i1-1][i2-1] + t
。
-
A从上方走到(i1,k-i1),B从左侧走到(i2,k-i2),即
f[k-1][i1-1][i2] + t
。
-
A从左侧走到(i1,k-i1),B从上方走到(i2,k-i2),即
f[k-1][i1][i2-1] + t
。
-
A从左侧走到(i1,k-i1),B从左侧走到(i2,k-i2),即
f[k-1][i1][i2] + t
。
其中如果i1不等于i2,那么t等于a[i1][k-i1] + a[i2][k-i2];如果i1等于i2,那么t等于a[i1][k-i1]。
C++代码如下,
#include <iostream>
using namespace std;
const int N = 15;
int n;
int a[N][N];
int f[2 * N][N][N];
int main() {
cin >> n;
int i, j, w;
while (cin >> i >> j >> w, i || j || w) {
a[i][j] = w;
}
for (int k = 2; k <= 2 * n; ++k) {
for (int i1 = 1; i1 <= k; ++i1) {//i1循环到k
for (int i2 = 1; i2 <= k; ++i2) {//i2也循环到k
int t = a[i1][k-i1];
if (i1 != i2) t += a[i2][k-i2];
int val1 = max(f[k-1][i1][i2], f[k-1][i1-1][i2-1]);
int val2 = max(f[k-1][i1][i2-1], f[k-1][i1-1][i2]);
f[k][i1][i2] = max(val1, val2) + t;
}
}
}
cout << f[2 * n][n][n] << endl;
return 0;
}