比赛时，没有想到用dp可以解决，结果。。。还是要多做题啊。

 

//  [4/13/2014 Sjm]/*状态：dp[i+1][j+1] := 第 i 幅画， 第 j 个画家所画完所话费的时间 ***********************************************************************分析：若第 j 个画家想要开始画第 i 幅画，则必须满足的两个条件是：1) 第 j-1 个画家已经画完了第 i 幅画；2) 第 j 个画家已经花完了第 i-1 幅画。由此可得出，第 j 个画家画完第 i 幅画的时间。（决策也就在两个条件中产生了。）*********************************************************************** 决策：dp[i + 1][j + 1] = max(dp[i+1][j], dp[i][j + 1]) + arr[i][j];

注意：数组作为全局变量，防止 Stack overflow*/

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int MAX_M = 50000, MAX_N = 5; 8 int  dp[MAX_M + 1][MAX_N + 1], arr[MAX_M][MAX_N]; 9 // 数组作为全局变量，防止 Stack overflow10 11 int main()12 {13     //freopen("input.txt", "r", stdin);14     //freopen("output.txt", "w", stdout);15     int m, n;16     scanf("%d %d", &m, &n);17     for (int i = 0; i < m; i++)18         for (int j = 0; j < n; j++)19             scanf("%d", &arr[i][j]);20     int mytime = 0;21     memset(dp, 0, sizeof(dp));22     for (int i = 0; i < m; i++) {23         for (int j = 0; j < n; j++) {24             dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]) + arr[i][j];25         }26         printf("%d ", dp[i + 1][n]);27     }28     return 0;29 }