UVA 690 PipelineScheduling 位运算+dfs+剪枝

一开始最容易想到间隔最多为n，但是结点还是太多了，需要优化。

预处理：预判一下并保存下一个可以放的位置距离之前的距离。这样可以减少很多判断。

最优化剪枝：如果当前长度+剩下没放的程序*最短间隔如果大于等于ans，那么对答案没有贡献，可以剪去。

优化：占用和不占用两种状态，如果横向来看可以压缩为int，判断时用上为运算。

此题挂在长度的枚举上，我把长度为n给忽略了，实际上可以只有一部分长度为n。

#include<bits/stdc++.h>

//using namespace std;

//#define local

const int maxn = ;

const int N = ;

int tab[N];

int ans;

int ivs[maxn],SZ;

void dfs(int d,int* pre,int len)

{

    if(len + ( - d)*ivs[] >= ans ) return;

    for(int i = ; i < SZ; i++){

        int iv  = ivs[i];

        bool ok = true;

        for(int j = ; j < N; j++) {

            if((pre[j]>>iv)&tab[j]) { ok = false; break;}

        }

        if(ok) {

            if(d == ) {

                ans = std::min(ans,len+iv);

                return ;

            }

            int now[N];

            for(int j = ; j < N; j++) {

                now[j] = (pre[j] >> iv) | tab[j];

            }

            dfs(d+,now,len+iv);

        }

    }

}

void preJudge(int n)

{

    SZ = ;

    for(int iv = ; iv <= n; iv++){

        bool ok = true;

        for(int i = ; i < N; i++) {

            if((tab[i]>>iv)&tab[i]) { ok = false; break;}

        }

        if(ok) ivs[SZ++] = iv;

    }

}

int main()

{

#ifdef local

    freopen("in.txt","r",stdin);

   // freopen("out.txt","w",stdout);

#endif // local

    int n;

    char G[maxn+];

    while(~scanf("%d",&n)&&n) {

        memset(tab,,sizeof(tab));

        for(int i = ; i < N; i++){

            scanf("%s",G);

            for(int j = ; j < n; j++) if(G[j] == 'X'){

                tab[i] |= <<j;

            }

        }

        ans = n*;

        preJudge(n);

        dfs(,tab,n);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

UVA 690 PipelineScheduling 位运算+dfs+剪枝

最新文章

热门文章