1 // Project name : 游船费问题 2 // File name    : main.cpp 3 // Author       : Izumu 4 // Date & Time  : Sat Jul 14 15:21:28 2012 5  6  7 #include 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 using namespace std;13 14 #define MAXN 11015 16 int a[MAXN][MAXN];17 18 int n;19 ///20 void dp()21 {22     // dp .. - - > > that's very important for this program23     for (int j = 2; j <= n; j++)24     {25         int min = a[1][j];26         for (int i = 2; i < j; i++)27         {28             if (a[i][j] < min)29             {30                 min = a[i][j];31             }32         }33 34         if ((a[0][j-1] + min) < a[0][j])35         {36             a[0][j] = a[0][j-1] + min;37         }38     }39 }40 ///41 void init()42 {43     // set all mem to 044     for (int i = 0; i <= n; i++)45     {46         for (int j = 0; j <= n; j++)47         {48             a[i][j] = 0;49         }50     }51     // input data to a[][]52     for (int i = 0; i < n; i++)53     {54         for (int j = i + 1; j <= n; j++)55         {56             cin >> a[i][j];57         }58     }59 }60 ///61 void output()62 {63     cout << a[0][n] << endl;64 }65 66 int main()67 {68     int time = 0;69     while (cin >> n)70     {71         init();72         dp();73         time++;74         cout << "Case " << time << ":" << endl;75         output();76     }77     return 0;78 }79 80 // end 81 // ism