解题思路:动态规划,贪心不能得到最大解
注意事项:三维数组提高解题效率
参考代码:
#include<bits/stdc++.h> #define N 50 using namespace std; int a[N][N][3]; //a[N][N][0]记录求解路径,a[N][N][1]存储的数据,a[N][N][2]部分解的结果 int n; void operate() { for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { if(a[i+1][j][2]>a[i+1][j+1][2]) { a[i][j][2]=a[i][j][2]+a[i+1][j][2]; } else { a[i][j][2]=a[i][j][2]+a[i+1][j+1][2]; a[i][j][0]=1; } } } } int main() { int m; cin>>m; while(m--) { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { cin>>a[i][j][1]; a[i][j][2]=a[i][j][1]; a[i][j][0]=0; } } operate(); cout<<a[1][1][2]<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { a[i][j][0]=0; a[i][j][1]=0; a[i][j][2]=0; } } } return 0; }
0.0分
0 人评分
程序员的表白 (C语言代码)浏览:1463 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:677 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:858 |
【明明的随机数】 (C语言代码)浏览:785 |
【矩阵】 (C++代码)浏览:940 |
Hello, world! (C++代码)浏览:1744 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:825 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:545 |
剪刀石头布 (C语言代码)浏览:1433 |
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:653 |