---

底下有附上我的程式碼, WA, 時間複雜度n^2 *m

從左上到右下的DP, 子問題的分析如下:

問矩陣 [i, j] 之內的最佳組法, 假如包含元素a_ij, 則有兩種可能

1.包含a_kj 到 a_ij 的元素, 其中 k <= i, 則可以和左邊 "包含 a_k,j-1 到 a_i,j-1" 的最佳組合合併

2.包含a_kj 到 a_ij 的元素, 但直接往左延伸都不好, 只能找 a_k-1,j 的左上角

 

假如不包含元素a_ij,  則矩陣 [i, j] 內最佳解法一定在 [i-1, j] 或 [i, j-1]

 

//可以直接看三層迴圈那邊

 

 

 

 

 

 

 

 

#include<stdio.h>

#include<stdlib.h>

int Max(int a, int b)

{

if (a > b)

return a ;

return b ;

}

 

int main()

{

int n, m ;

scanf("%d %d",&n,&m);

 

    int **arr = new int*[n+1];

    int **ans = new int*[n+1];

    for(int i = 0 ; i <= n ; i++)

    {

        arr[i] = new int[m+1]{0};

        ans[i] = new int[m+1]{0};

    }

 

 

int ***dp = new int**[n+1];

for(int i = 0 ; i <= n ; i++)

{

dp[i] = new int*[m+1];

for(int j = 0 ; j <= m ; j++)

    dp[i][j] = new int[n+1]{0};

}

 

 

for(int i = 1 ; i <= n ; i++)

{

for(int j = 1 ; j <= m ; j++)

scanf("%d",&arr[i][j]);

}

 

for(int i = 1 ; i <= n ; i++)

{

for(int j = 1 ; j <= m ; j++)

{

int area = 0 ;

for(int k = i ; k >= 1 ; k--)//從 arr[i][j] 往上長

{

area += arr[k][j];

dp[i][j][k] = dp[i][j-1][k] + area;//可能可以往左延伸

 

//或者不能往左延伸, 只能找左上角最佳解

dp[i][j][k] = Max(area + ans[k-1][j-1], dp[i][j][k]);

 

ans[i][j] = Max(ans[i][j], dp[i][j][k]);

}

//ans[i][j] 可能是不含a_ij, 所以是另外兩塊的最佳解

ans[i][j] = Max(ans[i][j], ans[i][j-1]);

ans[i][j] = Max(ans[i][j], ans[i-1][j]);

}

}

printf("%d\n",ans[n][m]);

 

---

底下有附上我的程式碼, WA, 時間複雜度n^2 *m

從左上到右下的DP, 子問題的分析如下:

問矩陣 [i, j] 之內的最佳組法, 假如包含元素a_ij, 則有兩種可能

1.包含a_kj 到 a_ij 的元素, 其中 k <= i, 則可以和左邊 "包含 a_k,j-1 到 a_i,j-1" 的最佳組合合併

2.包含a_kj 到 a_ij 的元素, 但直接往左延伸都不好, 只能找 a_k-1,j 的左上角

 

假如不包含元素a_ij,  則矩陣 [i, j] 內最佳解法一定在 [i-1, j] 或 [i, j-1]

 

//可以直接看三層迴圈那邊

 

 

 

 

 

 

 

 

#include

#include

int Max(int a, int b)

{

if  (a > b)

return a ;

return b ;

}

 

int main()

{

int n, m ;

scanf("%d %d",&n,&m);

 

int **arr = new int*[n+1];

int **ans = new int*[n+1];

    for(int i = 0 ; i <= n ; i++)

    {

        arr[i] = new int[m+1]{0};

        ans[i] = new int[m+1]{0};

    }

 

 

int ***dp = new int**[n+1];

for(int i = 0 ; i <= n ; i++)

{

dp[i] = new int*[m+1];

for(int j = 0 ; j <= m ; j++)

    dp[i][j] = new int[n+1]{0};

}

 

 

for(int i = 1 ; i <= n ; i++)

{

for(int j = 1 ; j <= m ; j++)

scanf("%d",&arr[i][j]);

}

 

for(int i = 1 ; i <= n ; i++)

{

for(int j = 1 ; j <= m ; j++)

{

int area = 0 ;

for(int k = i ; k >= 1 ; k--)//從 arr[i][j] 往上長

{

area += arr[k][j];

dp[i][j][k] = dp[i][j-1][k] + area;//可能可以往左延伸

 

//或者不能往左延伸, 只能找左上角最佳解

dp[i][j][k] = Max(area + ans[k-1][j-1], dp[i][j][k]);

 

ans[i][j] = Max(ans[i][j], dp[i][j][k]);

}

//ans[i][j] 可能是不含a_ij, 所以是另外兩塊的最佳解

ans[i][j] = Max(ans[i][j], ans[i][j-1]);

ans[i][j] = Max(ans[i][j], ans[i-1][j]);

}

}

printf("%d\n",ans[n][m]);

結果我的想法是對的, 只是要用長整數儲存...有人有更好作法嗎?第一子題有人只要幾十毫秒, 如果只是特別把這一子題以其他演算法解決, 那就算了