P2258-子矩阵

╰半夏微凉° 2023-06-01 08:52 22阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 
     4 typedef long long ll;
     5 using namespace std;
     6 inline ll read()
     7 {
     8     ll ans = 0;
     9     char ch = getchar(), last = ' ';
    10     while(!isdigit(ch)) last = ch, ch = getchar();
    11     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    12     if(last == '-') ans = -ans;
    13     return ans;
    14 }
    15 inline void write(ll x)
    16 {
    17     if(x < 0) x = -x, putchar('-');
    18     if(x >= 10) write(x / 10);
    19     putchar(x % 10 + '0');
    20 }
    21 int n,m,r,c;
    22 int num[18][18];
    23 int dp[18][18];
    24 int lc[18],hc[18][18];
    25 int df[20] = {
        0},dfend = 1;
    26 int rnt = 0x3f3f3f3f;
    27 void pre()
    28 {
    29     memset(lc,0,sizeof(lc));
    30     memset(hc,0,sizeof(hc));
    31     _for(i,1,r)
    32         _for(j,1,m+1)
    33             lc[j] += abs(num[df[i]][j]-num[df[i+1]][j]);
    34     _for(i,1,m+1)
    35         _for(j,i+1,m+1)
    36             _for(k,1,r+1)
    37                 hc[i][j] += abs(num[df[k]][i]-num[df[k]][j]);
    38 }
    39 
    40 void pick()
    41 {
    42     _for(i,1,m+1)
    43     {
    44         _for(j,1,min(c+1,i+1))
    45         {
    46             if(1==j)
    47                 dp[i][j] = lc[i];
    48             else
    49             {
    50                 dp[i][j] = 0x3f3f3f3f;
    51                 for(int k = j-1; k < i; k ++)
    52                     dp[i][j] = min(dp[i][j],dp[k][j-1]+lc[i]+hc[k][i]);
    53             }
    54         }
    55         if(i>=c)
    56             rnt = min(rnt,dp[i][c]);
    57     }
    58 }
    59 void dfs(int ii)
    60 {
    61     if(ii>n)
    62     {
    63         pre();
    64         pick();
    65         return ;
    66     }
    67     if(r-dfend==n-ii)
    68     {
    69         df[dfend++] = ii;
    70         dfs(ii+1);
    71         dfend --;
    72         return ;
    73     }
    74     dfs(ii+1);
    75     if(dfend<=r)
    76     {
    77         df[dfend++] = ii;
    78         dfs(ii+1);
    79         dfend --;
    80     }
    81 }
    82 
    83 void solve()
    84 {
    85     dfs(1);
    86 }
    87 
    88 int main()
    89 {
    90     n = read(), m = read(),r = read(),c = read();
    91 
    92     _for(i,1,n+1)
    93         _for(j,1,m+1)
    94             num[i][j] = read();
    95     solve();
    96     write(rnt);
    97     return 0;
    98 }

转载于:https://www.cnblogs.com/Asurudo/p/11373464.html