【习题 7-5 UVA-690】Pipeline Scheduling

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

一定在这里写完思路再敲代码!!!

处理出5个工作单元在哪些时刻会被用到。

->设为initstatu

因为每次都会面临之前已经用了一段程序,而现在要走下一步的情况

->但有一些地方是肯定已经不能走了的。

->我们可以预处理出来哪些地方是可以走的。

->剩下的.可能不能走.我们再额外处理就好

->这样可以节省很多的时间。

然后在搜索的时候.维护长度为n的statu.

(即不断更新末尾那一段,哪个时间是不能用的->有冲突的

假设要在偏移量为i的地方开始下一个程序。

直接看看statu>>i 和initstatu的and值是不是大于0.

(是一个5维的statu

等于0就说明可以放

然后更新状态。

statu = (statu>>i)&(initstatu);

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 20+5;

int initstatu[10],n,nowstatu[10],ans = 1e8;

int can[N];

char s[N];

bool ok(int *nowstatu,int d){

    for (int i = 1;i <= 5;i++){

        if ((nowstatu[i]>>d)&initstatu[i]) return false;

    }

    return true;

}

void dfs(int dep,int s){

    if (s+n>ans) return;

    if (dep > 10){

        ans = min(ans,s+n);

        return;

    }

    if (s+n+(10-dep)*can[1]>ans) return;

    int tempstatu[10];

    for (int d = 1;d <= can[0];d++){

        if (!ok(nowstatu,can[d])) continue;

        //ok

        //getnewstate

        for (int i = 1;i <= 5;i++) tempstatu[i] = nowstatu[i];

        for (int i = 1;i <= 5;i++) nowstatu[i] = (nowstatu[i]>>can[d])|initstatu[i];

        dfs(dep+1,s+can[d]);

        for (int i = 1;i<= 5;i++) nowstatu[i] = tempstatu[i];

    }

}

int main(){

	#ifdef LOCAL_DEFINE

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

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    while (cin >> n && n){

        memset(initstatu,0,sizeof initstatu);

        for (int i = 1;i <= 5;i++){

            cin >> (s+1);

            int now = 1;

            for (int j = 1;j <= n;j++){

                if (s[j]=='X') initstatu[i] |= now;

                now = now*2;

            }

        }

        can[0] = 0;

        for (int i = 1;i <= n;i++)

            if (ok(initstatu,i)){

                can[0]++;

                can[can[0]] = i;

            }

        for (int i = 1;i <= 5;i++) nowstatu[i] = initstatu[i];

        ans = n*10;

        dfs(2,0);

        cout << ans << endl;

    }

	return 0;

}