数字三角形WriteUp
题目:
题目截图:
YXC AC源代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
cin >> f[i][j];
for (int i = n - 1; i; i -- )
for (int j = 1; j <= i; j ++ )
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
cout << f[1][1] << endl;
return 0;
}
Lxxx AC源代码:
#include <iostream>
#include <cstring>
#include <algorithm>
const int N=510;
using namespace std;
int f[N][N];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> f[i][j];
}
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
}
}
cout << f[1][1] << endl;
return 0;
}
题目分析(DP 动态规划):
OI坐标轴与数学坐标轴的区别如下图所示:
利用闫氏DP分析法如下:
由于这道题,从上至下考虑需要加一些特判,而从下至上考虑就不需要。
因此这道题采用从下至上的思路。
其中f(i,j)表示从下至上走的所有路线的集合
这里的f(i,j)的属性,根据题目,属性值为最大值
假设w(i,j)表示处于(i,j)位置的数字
则,利用闫氏DP分析法可以得出下方表达式
代码编写:
以下是原代码:
#include <iostream>
#include <cstring>
#include <algorithm>
const int N=510;
using namespace std;
int w[N][N],f[N][N];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> w[i][j];
}
}
for(int i=1;i<=n;i++){
f[n][i]=w[n][i];
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
}
}
cout << f[1][1] << endl;
return 0;
}
合并f,w数组,将下方代码进行等价变形
变形之后的代码如下:
最后整理之后的代码如下:
#include <iostream>
#include <cstring>
#include <algorithm>
const int N=510;
using namespace std;
int f[N][N];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> f[i][j];
}
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
}
}
cout << f[1][1] << endl;
return 0;
}