題目傳送
表示一開始也是一臉懵逼
，雖然想到了DP，但面對多變的狀态不知從何轉移及怎麼合理記錄狀态。之（借鑒大佬思路）後，豁然開朗，于是在AC後分享一下題解。
發現資料範圍出奇地小，不過越是小的資料範圍，算法的靈活性就越大。小資料對我們各個算法的組合及時間複雜度的掌握要求很高。面對二維的最優化選擇，其實我們可以先通過搜尋枚舉出行的所有選擇，存到一個數組team中，然後在行已經确認的情況下，跑一遍一維的DP：設dp[j][i]為在前j列選擇i列的最優情況（為了友善，要求第i選擇的列一定是第j列）。則狀态轉移方程就可寫成：dp[j][i]=min(dp[j][i],dp[k][i-1]+lc[j]+hc[k][j]），其中lc為第j列的分值，hc[k][j]為第k列和第j列橫向相鄰元素對分值的貢獻，k=i-1,i-1+1,...,j-1。對于lc和hk
我們可以在每次搜尋完成後預處理一下，整個程式的時間複雜度即為O（C（n,r）*rm2）,足以解出題。
代碼上有一個小優化，詳情見注釋：
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4
5 using namespace std;
6
7 int n, m, r, c, num[17][17], ans = 0x7fffffff, team[17], lteam;
8 int lc[17]; //列
9 int hc[17][17]; //列之間
10 int dp[17][17];
11
12 void init()
13 {
14 for (int i = 1; i <= m; i++)
15 {
16 lc[i] = 0;
17 for (int j = 1; j < r; j++)
18 lc[i] += abs(num[team[j]][i] - num[team[j + 1]][i]);
19 }
20 for (int i = 1; i < m; i++)
21 for (int j = i + 1; j <= m; j++)
22 {
23 hc[i][j] = 0;
24 for (int k = 1; k <= r; k++)
25 hc[i][j] += abs(num[team[k]][i] - num[team[k]][j]);
26 }
27 }
28
29 void DP()
30 {
31 for (int i = 1; i <= m; i++)
32 dp[i][1] = lc[i];
33 if (c == 1)
34 {
35 for (int i = 1; i <= m; i++)
36 ans = ans > dp[i][1] ? dp[i][1] : ans;
37 return;
38 }
39 for (int i = 2; i <= c; i++)
40 {
41 for (int j = i; j <= m - c + i; j++)
42 {
43 dp[j][i] = 0x2fffffff;
44 for (int k = j - 1; k >= i - 1; k--)
45 dp[j][i] = min(dp[j][i], dp[k][i - 1] + lc[j] + hc[k][j]);
46 }
47 }
48 for (int i = c; i <= m; i++)
49 ans = min(ans, dp[i][c]);
50 }
51
52 void dfs(int now)
53 {
54 if (now > n)//選擇完畢
55 {
56 init();
57 DP();
58 return;
59 }
60 if (r - lteam == n - now + 1)//當剩下的元素與還要選擇的元素的數量相等時，必須要選
61 {
62 team[++lteam] = now;
63 dfs(now + 1);
64 --lteam;
65 return;
66 }
67 dfs(now + 1);//目前行要麼不選
68 if (lteam < r)//要麼在符合條件的情況下選
69 {
70 team[++lteam] = now;
71 dfs(now + 1);
72 --lteam;
73 }
74 }
75
76 int main()
77 {
78 scanf("%d%d%d%d", &n, &m, &r, &c);
79 for (int i = 1; i <= n; i++)
80 for (int j = 1; j <= m; j++)
81 scanf("%d", &num[i][j]);
82 dfs(1);
83 printf("%d", ans);
84 return 0;
85 } 轉載于:https://www.cnblogs.com/InductiveSorting-QYF/p/11095230.html