1.数字三角形。acwing 898.
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N = 520,INF = 1e9; 5 int n; 6 int a[N][N]; //表示每一个点 7 int f[N][N]; //表示状态 8 9 int main() 10 { 11 cin >> n; 12 for (int i = 1; i <= n; i ++ ) 13 for (int j = 1; j <= i; j ++ ) 14 cin >> a[i][j]; 15 16 for (int i = 0; i <= n; i ++ ) 17 for (int j = 0; j <= i + 1; j ++ ) //每行多初始化一个,表示三角形最右边的右上角表示负无穷 18 f[i][j] = -INF; //避免处理边界情况,先将状态初始化为负无穷 19 20 f[1][1] = a[1][1]; 21 22 for (int i = 2; i <= n; i ++ ) 23 for (int j = 1; j <= i; j ++ ) 24 f[i][j] = max(f[i - 1][j - 1] + a[i][j],f[i - 1][j] + a[i][j]); 25 26 int res = -INF; 27 for (int i = 1; i <= n; i ++ ) //枚举三角形底边终点的状态的最大值 28 res = max(res,f[n][i]); 29 30 cout << res << endl; 31 32 return 0; 33 }View Code
标签:const,int,namespace,1e9,线性,dp From: https://www.cnblogs.com/rw666/p/17844611.html