fork download
copy 
  1. /**
  2.  *  Dynamic Programming - Triangle Problem
  3.  *  2
  4.  *  3 5
  5.  *  6 3 4
  6.  *  5 6 1 4
  7.  *
  8.  *  The new Triangle
  9.  *  C[i,j] = max(T[i,j]+C[i+1,j], T[i,j] + C[i+1,j+1])
  10.     where i apartine [1,n-1]
  11.  *  17
  12.  *  15 14
  13.  *  12 9 8
  14.  *   5 6 1 4
  15.  */
  16. #include <bits/stdc++.h>
  17. #define FIN "triangle.in"
  18. #define FOUT "triangle.out"
  19. #define SIZE 101
  20.  
  21. using namespace std;
  22.  
  23. int i,n,Tri[ SIZE ][ SIZE ],
  24.       C[ SIZE ][ SIZE ],
  25.       Road[ SIZE ][ SIZE ];
  26.  
  27. ifstream fin(FIN);
  28. ofstream fout(FOUT);
  29.  
  30. int main( int argc, char const *argv[] ) {
  31.  
  32.     cin>>n;
  33.  
  34.     for( int i = 1; i <= n; ++i )
  35.  
  36.         for(int j = 1; j <= i; ++j)
  37.  
  38.             cin>>Tri[i][j];
  39.  
  40.     for( int i = 1; i <= n; ++i ) {
  41.  
  42.         for(int j = 1; j <= i; ++j) {
  43.  
  44.                     cout<<Tri[i][j]<<" ";
  45.         }
  46.         cout<<endl;
  47.     }
  48.  
  49.     for(int j = 1; j <= n; ++j) C[n][j] = Tri[n][j];
  50.  
  51.     for(int i = n - 1; i >= 1; i--) {
  52.  
  53.         for(int j = 1; j <= i; ++j) {
  54.  
  55.             if(C[i+1][j] > C[i+1][j+1]) {
  56.  
  57.                 C[i][j] = Tri[i][j] + C[i+1][j];
  58.  
  59.                 Road[i][j] = j;
  60.  
  61.             } else {
  62.  
  63.                 C[i][j] = Tri[i][j] + C[i+1][j+1];
  64.  
  65.                 Road[i][j] = j+1;
  66.             }
  67.         }
  68.     }
  69.  
  70.     cout<<C[1][1]<<"\n";
  71.  
  72.     int i,j;
  73.     i = j = 1;
  74.     while(i<=n) {
  75.       cout<<Tri[i][j]<<" ";
  76.       j = Road[i][j];
  77.       i++;
  78.     }
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
5
4
1 4
9 9 3
9 4 4 3
4 5 2 5 6
stdout
copy 
4 
1 4 
9 9 3 
9 4 4 3 
4 5 2 5 6 
28
4 1 9 9 5
https://ideone.com/PJBk00
Triangle Problem DP
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!