dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + ver[i] + del[i - k][i]);
//第 i-k 列是第 i 列的上一列,所以應該要選擇j-1列
//加上新選的第 i 列的貢獻：第i列的上下絕對值差的和,第 i 列與第 i-k 列的左右絕對值差的和 

考慮 k 的范圍：首先我們是從第 i - k列中選了 j - 1列，那么 i - k 一定得大于等于 j - 1 吧（不然怎么選），其次我們要從第 i 列往前找 k 列來作為鄰列，那么顯然 i - k > 0

考慮邊界條件

注意到我們 dp 數組的第一維是要選上該列的，那么如果我們第二維只選一條列的話，那么肯定是選正在枚舉的這一列的，所以就有如下邊界設置：

    for (int i = 1; i <= m; i++)
        dp[i][1] = ver[i];                      //如果只選擇一列肯定是選自己 

上 dp 代碼：

    for (int i = 1; i <= m; i++)                //我們已經找了i列 
        for (int j = 1; j <= c; j++)            //我們一共只選擇c列 
            for (int k = 1; i - k > 0 && i - k >= j - 1; k++)    //找i的鄰列 
                dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + ver[i] + del[i - k][i]);   //狀態轉移方程 
//第 i-k 列是第 i 列的上一列,所以應該要選擇j-1列
//加上新選的第 i 列的貢獻：第i列的上下絕對值差的和,第 i 列與第 i-k 列的左右絕對值差的和 

考慮答案選擇

我們最終肯定是要只選擇 c 列的，所以我們要枚舉每種能夠選擇 c 列的情況，選擇最小得分即可：

    for (int i = c; i <= m; i++)//從c行后取最小值 
        ans = min(ans, dp[i][c]);

完整AC代碼（累死QwQ~）:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m, r, c, ans = 2147483647;
int a[19][19], hang[19], dp[19][19];
int ver[19], del[19][19]; 
/*
a[i][j]:矩陣第i行第j列的數;
dp[i][j]:枚舉列要用,表示前i列我們已經選了j列所得到的最小分值,注意要選第i列（這j列中包含第i列）;
ver[i]:第i列上下絕對值差的和;
del[i][j]:第i列和第j列左右絕對值差的和;
hang[i]:枚舉的子矩陣的第i行在原大矩陣的行數;
*/
inline void Dp()
{              
    memset(dp, 123, sizeof(dp));                //注意不要忘了清空 
    memset(ver, 0, sizeof(ver));
    memset(del, 0, sizeof(del));
    
    for (int i = 1; i <= m; i++)                //枚舉每一列
        for (int j = 2; j <= r; j++)            //枚舉子矩陣的每一行 
            ver[i] += abs(a[hang[j]][i] - a[hang[j - 1]][i]) ;   //利用hang數組回到原矩陣去尋找值 
            
    for (int i = 1; i <= m; i++)                //枚舉每一列 i 
        for (int k = i + 1; k <= m; k++)        //再找 i 之后的列 
            for (int j = 1; j <= r; j++)        //枚舉子矩陣的每一行 
                del[i][k] += abs(a[hang[j]][k] - a[hang[j]][i]); //套定義求出del數組 
    for (int i = 1; i <= m; i++)
        dp[i][1] = ver[i];                      //如果只選擇一列肯定是選自己 
    for (int i = 1; i <= m; i++)                //我們已經找了i列 
        for (int j = 1; j <= c; j++)            //我們一共只選擇c列 
            for (int k = 1; i - k > 0 && i - k >= j - 1; k++)    //找i的鄰列 
                dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + ver[i] + del[i - k][i]);   //狀態轉移方程 
//第 i-k 列是第 i 列的上一列,所以應該要選擇j-1列
//加上新選的第 i 列的貢獻：第i列的上下絕對值差的和,第 i 列與第 i-k 列的左右絕對值差的和 
    for (int i = c; i <= m; i++)//從c行后取最小值 
        ans = min(ans, dp[i][c]); 
}        
void dfs(int now, int pos)        //我們當前正在選第now行,這一行在原矩陣中是第pos行 
{
    if (now == r + 1)             //如果超出了r行,說明我們已經選完了r行,開始進行dp操作 
    {
        Dp();
        return;
    }
    if (pos == n + 1)             //判斷是否在原矩陣范圍內 
        return;
    for (int i = pos; i <= n; i++)//從第pos行開始往后選 
        hang[now] = i, dfs(now + 1, i + 1);  //繼續往下選 
//hang[now]=i :在子矩陣里的第now行就是原矩陣的第i行 
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &r, &c);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)    
            scanf("%d", &a[i][j]);
    dfs(1, 1);
    printf("%d", ans);
}

蟹蟹你的觀看QwQ~

總結

以上是生活随笔為你收集整理的P2258 子矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。