首先应该想到一点, 如果一段管道被中途截断了, 那么这段管道就是毫无意义的, 没了它答案也不会变差.

那么, 决策就可以看成每次修一条管道(从下到上或者从右到左), 状态可以定为每次考虑一个矩阵(顺序从小到大)

其次,很明显这个题满足最优子结构性质.

那么就不难写出方程了

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int MAXN = 5e2 + 20; 7 inline int read() 8 { 9     int x = 0; char ch = getchar();10     while(!isdigit(ch)) ch = getchar();11     while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();12     return x;13 }14 int N, M;15 int squ[MAXN][MAXN][2];16 int f[MAXN][MAXN];17 18 int main()19 {20     while(cin>>N>>M, N)21     {22         memset(squ, 0, sizeof(squ));23         for(int i = 1; i <= N; i++)24             for(int j = 1; j <= M; j++)25                 squ[i][j][0] = squ[i][j - 1][0] + read();26 27         for(int i = 1; i <= N; i++)28             for(int j = 1; j <= M; j++)29                 squ[i][j][1] = squ[i - 1][j][1] + read(); 30             31         memset(f, 0, sizeof(f));32         for(int i = 1; i <= N; i++)33             for(int j = 1; j <= M; j++)34                 f[i][j] = max(f[i][j], max(f[i][j - 1] + squ[i][j][1], f[i - 1][j] + squ[i][j][0]));35         cout<
         
          <