数字三角形模型
文章目录
- 一、数字三角形（裸题）
- 二、摘花生（场景题）
- 三、最低通行费用（场景题）
- 四、方格取数（场景题）
- 五、传纸条（场景题）
一、数字三角形（裸题）
题目链接
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int a[N][N];
int dp[N][N];
int n;
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= i;j ++)
cin >> a[i][j];
//从最后开始到初始状态，这样不需要考虑细节问题
for(int i = n;i >= 1;i --)
for(int j = i;j >= 1;j --)
{
if(i == n) dp[n][j] = a[n][j];
else
{
dp[i][j] = max(dp[i + 1][j] + a[i][j], dp[i + 1][j + 1] + a[i][j]);
}
}
cout << dp[1][1];
return 0;
}
二、摘花生（场景题）
题目链接
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int t;
int a[N][N];
int dp[N][N];
int main()
{
cin >> t;
while(t --)
{
int r,c;
cin >> r >> c;
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
cin >> a[i][j];
dp[1][1] = a[1][1];
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
{
dp[i][j] = max(dp[i - 1][j] + a[i][j], dp[i][j - 1] + a[i][j]);
}
cout << dp[r][c] << endl;
}
}
三、最低通行费用（场景题）
题目链接
这个题有一个隐含条件商人必须在2n - 1的时间内出去，证明商人只能向下或者向右走，不能往回走，往回走就无法走到终点
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int a[N][N];
int dp[N][N];
int n;
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
cin >> a[i][j];
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
{
//特殊处理如果是第一行的话只能从左边过来，第一列的话只能从上面下来
if(i == 1 && j == 1) dp[i][j] = a[1][1];
else if(i == 1) dp[i][j] = dp[i][j - 1] + a[i][j];
else if(j == 1) dp[i][j] = dp[i - 1][j] + a[i][j];
else
dp[i][j] = min(dp[i - 1][j] + a[i][j],dp[i][j - 1] + a[i][j]);
}
cout << dp[n][n];
return 0;
}
四、方格取数（场景题）
这里有一个问题，两个人为什么要同时走，而不是分开走？
如果分开走的话，每次都是贪心思维，这样可能会走漏掉某些地方，第一次的最优解 + 第二次的最优解 ！= 两次同时走的全局最优解
全局最优解的例子
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
int w[N][N];
int n;
int 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;
}
// i1 + j1 == i2 + j2 == k就不成立
for(int k = 2;k <= n + 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 t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];//这里i1!=i2也证明走的不是同一个点
//四种状态
int &x = f[k][i1][i2];
//右右
x = max(x, f[k - 1][i1][i2] + t);
//下下
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
//右下
x = max(x, f[k - 1][i1][i2 - 1] + t);
//下右
x = max(x, f[k - 1][i1 - 1][i2] + t);
}
}
printf("%d\n", f[n + n][n][n]);
return 0;
}
五、传纸条（场景题）
和上面一个题几乎一模一样
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 52;
int f[N*2][N][N];
int w[N][N];
int n,m;
int main()
{
cin >> m >> n;
for(int i = 1;i <= m;i ++)
for(int j = 1;j <= n;j ++)
cin >> w[i][j];
for(int k = 2;k <= n + m;k ++)
for(int i1 = 1;i1 <= m;i1 ++)
for(int i2 = 1;i2 <= m;i2 ++)
{
int j1 = k - i1, j2 = k - i2;
if(j1 >= 1 && j2 >= 1 && j1 <= n && j2 <= n)
{
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
//四种状态
int &x = f[k][i1][i2];
//右右
x = max(x, f[k - 1][i1][i2] + t);
//下下
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
//右下
x = max(x, f[k - 1][i1][i2 - 1] + t);
//下右
x = max(x, f[k - 1][i1 - 1][i2] + t);
}
}
cout << f[m + n][m][m];
return 0;
}