洛谷P2258 子矩阵——题解

Bertha 。 2021-11-26 07:26 287阅读 0赞

[题目传送][Link 1]

![1605498-20190627092835228-403173840.png][]

![1605498-20190627092852661-1011674391.png][]

![1605498-20190627092909341-457934184.png][]

![1605498-20190627092922519-1190641059.png][]

表示一开始也是一脸懵逼![1605498-20190627093035371-1614541238.png][]，虽然想到了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

[Link 1]: https://www.luogu.org/problemnew/show/P2258
[1605498-20190627092835228-403173840.png]: /images/20211126/5073eebfb70b488cb24c0805ac6e21c0.png
[1605498-20190627092852661-1011674391.png]: /images/20211126/d5b85d86cd9440249104cfaed3a20e2f.png
[1605498-20190627092909341-457934184.png]: /images/20211126/59bf0bb1b03d4f5684006abc3672e5d2.png
[1605498-20190627092922519-1190641059.png]: /images/20211126/1a316f3f12b943dca785498e1fb92d73.png
[1605498-20190627093035371-1614541238.png]: /images/20211126/9d5fbeed7e5e45e780bd7f16249ade75.png