A simple Blog for wyx I've been down the bottle hoping.
4707: B君的技巧 DP
发表于: | 分类: Oi | 评论:0 | 阅读:66

非常神奇的一个dp

首先我们完全不要考虑在这个矩阵上划范围dp,这个思路会陷入瓶颈然后无法解决

把矩阵作为正常的权值矩阵然后考虑直接在值域区间上大力dp

注意到一个非常奇怪的约定是他们二进制上的第$k$位必须是完全相同的,然后由于这个更大的块也会满足这个所以其实是他们前若干位一直到第$k$位都必须是完全相同的,不然就不会满足块更大的时候的需求

注意到这样的一段区间的取值和只标号的线段树上一段等长区间内取值是完全相同的,就是我们常写的那个k<<1以及k<<1|1

在到达一段区间前这段区间必然经历了相同的<<1<<1|1,所以二进制前缀相同

然后就好办了考虑dp

$f(x,l,r)$ 表示当前区间是标号为$x$的位置然后最左面的是$l$最右面的是$r$

大力枚举中间点转移就行

注意到不同$x$可取区间是完全不同的,想想线段树上等深度的若干区间就明白了,所以$x$一维压掉即可

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 512+5;
const int inf = 1e9;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int w[N][N], g[N][N], f[N][N], h[N][N];


int main() {
    int K = read(), n = 1 << K;
    int i,j,m=1,temp,l,r,mid,k;
    for(i=0;i<n;++i) for(j=0;j<n;++j) w[i][j] = read();
    while(K--) {
        temp = m; m <<= 1;
        for(l=0;l<n;l+=m) {
            r = l + m, mid = l + temp;
            for(i=l;i<mid;++i) for(j=mid;j<r;++j) {
                g[i][j] = inf;
                for(k=l;k<mid;++k) g[i][j] = min(g[i][j], f[i][k]+w[k][j]);
            }
            for(i=mid;i<r;++i) for(j=l;j<mid;++j) {
                g[i][j] = inf;
                for(k=mid;k<r;++k) g[i][j] = min(g[i][j], f[i][k]+w[k][j]);
            }
            for(i=l;i<mid;++i) for(j=mid;j<r;++j) {
                h[i][j] = inf;
                for(k=mid;k<r;++k) h[i][j] = min(h[i][j], g[i][k]+f[k][j]);
            }
            for(i=mid;i<r;++i) for(j=l;j<mid;++j) {
                h[i][j] = inf;
                for(k=l;k<mid;++k) h[i][j] = min(h[i][j], g[i][k]+f[k][j]);
            }
            for(i=l;i<r;++i) for(j=l;j<r;++j) f[i][j] = inf;
            for(i=l;i<mid;++i) for(j=mid;j<r;++j) f[i][j] = h[i][j];
            for(i=mid;i<r;++i) for(j=l;j<mid;++j) f[i][j] = h[i][j];
                /*
            for(i=l;i<r;++i)  {
                for(j=l;j<r;++j) 
                    cout << i << ' ' << j << ' ' << f[i][j] << endl;
            }*/
        }
    }
    int ans = inf;
    for(i=0;i<n;++i) for(j=0;j<n;++j) ans = min(ans, f[i][j]);
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP