ディジタルさんかくけいもんだい
3835 ワード
ディジタルさんかくけいもんだい
Description
次の図はデジタル三角形を示しています.プログラムを作成して、上から下までのどこかのパスを計算して、そのパスが通る数字と最大を計算してください.
Input
複数のテストケースがあり、各テストケースについて、キーボードで行単位で入力し、1行目は入力整数(この整数が0の場合は終了を表し、再処理は不要)で、三角形の行数n、次いでnの行数を表す
Output
最大値を出力
Example Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Example Output
30
コードブロック
#include
#include
#define MAX 1000
using namespace std;
int data[MAX][MAX]; //
int dp[MAX][MAX]; //
int tower_walk(int n)
{
//dp
for(int i=0; i1][i] = data[n-1][i];
int temp_max; //
for(int i=n-2; i>=0; i--)
for(int j=0; j<=i; j++)
{
temp_max = max(dp[i+1][j],dp[i+1][j+1]);
dp[i][j] = temp_max + data[i][j];
}
}
//
int print(int n)
{
cout << " :" << dp[0][0] << endl;
int node_value;
//
cout << " :" << data[0][0];
int j=0;
for(int i=0; iif(node_value == dp[i][j+1])
j++;
cout << " -> " << data[i][j];
}
cout << endl;
}
int main()
{
int n; // n
cin >> n;
for(int i=0; ifor(int j=0; j<=i; j++)
cin >> data[i][j];
tower_walk(n);
cout << dp[0][0] << endl; // dp[0][0]
return 0;
}