P2258 子矩阵
暴力枚举选行的情况，然后dp求选列的最优情况。
f[i][j]表示选了i行，最后一次选的是j列的情况。。。
c++代码如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cstring> #define rep(i,x,y) for(register int i = x;i <= y; ++ i) #define repd(i,x,y) for(register int i = x;i >= y; -- i) #define abs(x) (x > 0 ? x : -(x)) using namespace std; typedef long long ll; template<typename T>inline void read(T&x) { x = 0;char c;int sign = 1; do { c = getchar();if(c == '-') sign = -1; }while(c < '0' || c > '9'); do { x = x * 10 + c - '0'; c = getchar(); }while(c <= '9' && c >= '0'); x *= sign; } const int N = 17; int n,m,r,c,x,ans = 1e9+7; int w[N][N],f[N][N],sum[N][N],t[N]; bool vis[N]; void solve() { memset(sum,0,sizeof sum); memset(t,0,sizeof t); memset(f,0x3f,sizeof f); rep(i,1,m) { int last;bool e = 0; rep(j,1,n) if(vis[j]) { if(e) t[i] += abs(w[j][i] - last); e = 1;last = w[j][i]; } } rep(i,1,m) rep(j,1,i - 1) rep(k,1,n) if(vis[k]) sum[j][i] += abs(w[k][i] - w[k][j]); rep(i,1,m) f[1][i] = t[i]; rep(i,1,m) rep(k,1,i - 1) rep(j,1,c) f[j][i] = min(f[j][i],sum[k][i] + t[i] + f[j - 1][k]); rep(i,1,m) ans = min (ans,f[c][i]); } void dfs(int x,int z) { if(z == r) solve(); if(x > n || z == r) return; vis[x] = 1; dfs(x + 1,z + 1); vis[x] = 0; dfs(x + 1,z); } int main() { read(n);read(m);read(r);read(c); rep(i,1,n) rep(j,1,m) read(w[i][j]); dfs(1,0); cout<<ans<<endl; return 0; } |