需要锦州网站建设,wordpress 招聘网站,网站开发实习生,品质好的四字词语网址如下#xff1a;
Pipeline Scheduling - UVA 690 - Virtual Judge (vjudge.net)
#xff08;第三方网站#xff09; 噫#xff0c;好#xff01;我中了#xff01;
这题还是有点折磨的#xff0c;刚开始我只会递归下一个程序运行的时间#xff08;范围在1~n
Pipeline Scheduling - UVA 690 - Virtual Judge (vjudge.net)
第三方网站 噫好我中了
这题还是有点折磨的刚开始我只会递归下一个程序运行的时间范围在1~n很明显直接TLE然后用CSTL里面的bitset容器来表示所有的程序运行状况因为最差情况下最长的时间段是200用longlong只有64位不够表示结果vjudge上直接表示Compile Error应该是不能用
最后是上CSDN上去看其他人的解题思路
http://t.csdnimg.cn/AxOel
其中把时间段200缩短到20的方法启发了我而且里面提到的jump数组也减少的了递归量
妙哉
按这个思路自己写了一下之后是AC了 代码如下
#includecstdio
#includecstring
typedef long long LL;const int maxn 20;LL unit[5];
int jump[maxn], cnt;//jump的个数
int n, ans;void init(void){memset(unit, 0, sizeof(unit));ans n * 10; getchar(); cnt 0;
}
void getjump(void){LL unit_t[5]; memcpy(unit_t, unit, sizeof(unit));for(int i 1; i n; i){bool is true;for(int j 0; j 5; j){unit_t[j] 1;if(unit[j] unit_t[j]) is false;}if(is) jump[cnt] i;}
}
void dfs(LL state[5], int sum, int m){//剪枝if(sum jump[0] * (10 - m) ans) return;//尝试部署for(int i 0; i 5; i) if(unit[i] state[i]) return;//部署for(int i 0; i 5; i) state[i] | unit[i];//下一个if(m 10) ans sum;elsefor(int i 0; i cnt; i){int val jump[i];LL * p new LL [5];for(int j 0; j 5; j) p[j] state[j] val;dfs(p, sum val, m 1);delete [] p;}
}int main(void)
{while(scanf(%d, n) 1 n){//初始化init();//输入for(int i 0; i 5; i){int tmp 1; char c;for(int j 0; j n; j, tmp 1)if((c getchar()) X) unit[i] | tmp;getchar();}//得出答案getjump(); LL state[5]{};dfs(state, n, 1);printf(%d\n, ans);}return 0;
}
