表示一开始也是一脸懵逼,虽然想到了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 }