输入包含多组。每组数据的第一行包含一个正整数n(1≤n≤100),代表三角形的层数。
紧接着有n行数字,第i(1≤i≤n)行包含i个自然数。
对应每组数据,输出最大的和。
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
30
#include<iostream>#include<vector>usingnamespacestd;intmain(){intn;while(cin>>n){vector<vector<int>> input(n,vector<int>(n));for(inti=0;i<n;i++){for(intj=0;j<=i;j++)cin>>input[i][j];}for(inti=n-2;i>=0;i--){for(intj=0;j<=i;j++){input[i][j]+=max(input[i+1][j],input[i+1][j+1]);}}cout<<input[0][0]<<endl;}return0;}
while True:
try:
***, length = [], int(input())
for i in range(length):
***.append(list(map(int, input().split())))
for i in range(1, length):
***[i][0] += ***[i - 1][0]
***[i][-1] += ***[i - 1][-1]
for i in range(2, length):
for j in range(1, i):
***[i][j] += max(***[i - 1][j - 1], ***[i - 1][j])
print (max(***[-1]))
except:
break
#include<iostream> #include<vector> using namespace std; int main() { int n; while(cin>>n) { vector<vector<int>> input(n,vector<int>(n)); for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) cin>>input[i][j]; } for(int i=n-2;i>=0;i--) { for(int j=0;j<=i;j++) { input[i][j]+=max(input[i+1][j],input[i+1][j+1]); } } cout<<input[0][0]<<endl; } return 0; }
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<functional> #include <map> #include <set> #include <unordered_set> #include <unordered_map> #include <exception> #include <iomanip> #include <memory> #include <sstream> using namespace std; int main(int argc, char** argv) { //freopen("in.txt", "r", stdin); int n; while (cin >> n && n > 0) { vector<vector<int>> dp(n + 1, vector<int>(n + 1,0)); int num; for (int i = 1; i <= n; ++i) { cin >> num; dp[i][1] = dp[i - 1][1] + num; for (int j = 2; j <= i; ++j) { cin >> num; if (j == i) dp[i][j] = dp[i - 1][j - 1] + num; else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num; } } int maxPath = 0; for (auto& i : dp[n]) maxPath = max(maxPath, i); cout << maxPath << endl; } return 0; }
#include<iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; while (cin >> n) { // 数据输入 vector<vector<int> > d(n, vector<int>(n)); for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) cin >> d[i][j]; // 初始化f数组 vector<vector<int> > f(n, vector<int>(n)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) f[i][j]=0; f[0][0] = d[0][0]; // 从上往下迭代计算 - 标准动态规划 for (int i = 0; i < n-1; i++) for (int j = 0; j <= i; j++) { f[i + 1][j] = max(f[i + 1][j], f[i][j] + d[i + 1][j]); f[i + 1][j + 1] = max(f[i+1][j+1],f[i][j]+d[i+1][j+1]); } // 找出最大结果,输出 sort(f[n - 1].begin(), f[n - 1].end()); cout << f[n - 1][n-1] << endl; } return 0; }
#include<iostream> #include<vector> using namespace std; int main(){ int n; while(cin>>n){ vector<vector<int> > arr(n); for(int i=0;i<n;i++){ for(int j=0;j<i+1;j++){ int num=0; cin>>num; arr[i].push_back(num); } } vector<vector<int> > dp(n,vector<int>(n,0)); dp[0][0]=arr[0][0]; for(int i=1;i<n;i++) dp[i][0]=dp[i-1][0]+arr[i][0]; for(int i=1;i<n;i++) dp[i][arr[i].size()-1]=arr[i][arr[i].size()-1]+dp[i-1][arr[i-1].size()-1]; for(int i=2;i<n;i++){ for(int j=1;j<i;j++){ int temp=dp[i-1][j-1]>dp[i-1][j]? dp[i-1][j-1]:dp[i-1][j]; dp[i][j]=arr[i][j]+temp; } } int ans=0; for(int i=0;i<n;i++){ if(ans<dp[n-1][i]) ans=dp[n-1][i]; } cout<<ans<<endl; } return 0; }
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; while (cin >> n) { vector<vector<int> > m; for (int i = 0; i < n; ++i) { vector<int> cell(i + 1, 0); for (int j = 0; j <= i; ++j) cin >> cell[j]; m.push_back(cell); } for (int i = n - 2; i >= 0; --i) for (int j = 0; j <= i; ++j) m[i][j] += max(m[i + 1][j], m[i + 1][j + 1]); cout << m[0][0] << endl; } return 0; }
import java.util.Scanner; public class Main { public static int MaxSum(int x,int y,int N,int[][] array,int[][] maxSum ) { if(maxSum[x][y]!=-1) { return maxSum[x][y]; } if(x==N-1) { return maxSum[x][y]=array[x][y]; } else { int xx=MaxSum(x+1,y,N,array,maxSum); int yy=MaxSum(x+1,y+1,N,array,maxSum); maxSum[x][y]=Math.max(xx,yy)+array[x][y]; return maxSum[x][y]; } } public static void main(String[] args) { int N; Scanner reader =new Scanner(System.in); while(reader.hasNextInt()) { N = reader.nextInt(); int[][] array=new int [N][N]; int[][] maxSum=new int[N][N]; for(int i=0;i<N;i++) { for(int j=0;j<=i;j++) { maxSum[i][j]=-1; } } for(int i=0;i<N;i++) { for(int j=0;j<=i;j++) { array[i][j]=reader.nextInt(); } } System.out.println(MaxSum(0,0,N,array,maxSum)); } } }
while True: try: n = int(input()) res = [list(map(int,input().split())) for i in range(n)] for i in range(n-2,-1,-1): for j in range(i+1): res[i][j] = res[i][j] + max(res[i+1][j],res[i+1][j+1]) print(res[0][0]) except:break
/数塔问题/
#include<stdio.h>
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n;
int i,j;
while(scanf("%d",&n)!=EOF){
int matrix[n][n];
int dp[n][n];
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
scanf("%d",&matrix[i][j]);
dp[i][j]=matrix[i][j];
}
}
//前面是输入操作
//下面是从下往上选最大的,dp[i][j]表示到matrix[i][j]所累积的最大值
for(i=n-2;i>=0;i--){
for(j=i;j>=0;j--){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+matrix[i][j];
}
}
printf("%d\n",dp[0][0]);
}
}
#include <bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n) { int a[100][100] = {0}; for (int i = 0; i < n; ++i) for (int j = 0; j <= i; ++j) cin >> a[i][j]; int maxPath = a[0][0]; for (int i = 1; i < n; ++i) { for (int j = 0; j <= i; ++j) { a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]); maxPath = max(maxPath, a[i][j]); } } cout << maxPath << endl; } return 0; }
import java.util.Scanner; public class TrangleDemo { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()) { int n=sc.nextInt(); int[][] nums=new int[n][n]; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { nums[i][j]=sc.nextInt(); } } int[][] dp=new int[n][n]; for(int i=n-1;i>=0;i--) { for(int j=0;j<=i;j++) { if(i==n-1) { dp[i][j]=nums[i][j]; }else { dp[i][j]=Math.max(dp[i+1][j]+nums[i][j], dp[i+1][j+1]+nums[i][j]); } } } System.out.println(dp[0][0]); } } }
import java.util.Scanner; /** * Created by Olive on 2017/9/7. * <p> * 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 * 如上图所示,从一个数字三角形的顶部走到底部有很多条不同的路径, * 规则是只能从当前节点走到下一层相邻的节点,即下一层的左边或右边。 * 例如第三行第二个数字“1”只能走到第四行的第二个数字“7”与第三个数字“4”。 * 请寻找最佳一条路径,使得这条路径上节点的数字总和最大。 */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[][] array = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) array[i][j] = in.nextInt(); } System.out.println(findMax(array, n)); } } public static int findMax(int[][] array, int n) { if (array == null || array.length == 0 || array[0].length == 0 || n == 0) return 100; // dp[i][j]表示选择了第i层的第j个数字作为结尾的最大和 int[][] dp = new int[n + 1][n + 1]; int max = 0; // 第一行只能由上一层第一行访问 for (int i = 1; i <= n; i++) { dp[i][1] = dp[i - 1][1] + array[i][1]; } for (int i = 2; i <= n; i++) { for (int j = 2; j <= i; j++) { dp[i][j] = Math.max(dp[i - 1][j - 1] , dp[i - 1][j]) + array[i][j]; if (dp[i][j] > max) max = dp[i][j]; } } return max; } }
// write your code here cpp #include <iostream> #include <algorithm> using namespace std; int main(){ int n; while( cin>>n&&n>0){ int *maxSum; int num[101][101]; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>num[i][j]; maxSum=num[n]; for(int i=n-1;i>=1;--i) for(int j=1;j<=i;++j) maxSum[j]=max(maxSum[j],maxSum[j+1])+num[i][j]; cout<<maxSum[1]<<endl; } }
#include <iostream> #include <algorithm> using namespace std; int d[100][100]; int result[100][100]; int dp(int i,int j,int n){ if(i==n-1) { result[i][j]=d[i][j]; return result[i][j]; } if(result[i][j]!=-1) return result[i][j]; else{ int x=dp(i+1,j,n); int y=dp(i+1,j+1,n); result[i][j]=max(x,y)+d[i][j]; return result[i][j]; } } int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ cin>>d[i][j]; result[i][j]=-1; } } cout<<dp(0,0,n)<<endl; } return 0; }