一开始最容易想到间隔最多为n,但是结点还是太多了,需要优化。
预处理:预判一下并保存下一个可以放的位置距离之前的距离。这样可以减少很多判断。
最优化剪枝:如果当前长度+剩下没放的程序*最短间隔如果大于等于ans,那么对答案没有贡献,可以剪去。
优化:占用和不占用两种状态,如果横向来看可以压缩为int,判断时用上为运算。
此题挂在长度的枚举上,我把长度为n给忽略了,实际上可以只有一部分长度为n。
#include<bits/stdc++.h>
//using namespace std;
//#define local
const int maxn = 20;
const int N = 5;
int tab[N];
int ans;
int ivs[maxn],SZ;
void dfs(int d,int* pre,int len)
{
if(len + (10 - d)*ivs[0] >= ans ) return;
for(int i = 0; i < SZ; i++){
int iv = ivs[i];
bool ok = true;
for(int j = 0; j < N; j++) {
if((pre[j]>>iv)&tab[j]) { ok = false; break;}
}
if(ok) {
if(d == 9) {
ans = std::min(ans,len+iv);
return ;
}
int now[N];
for(int j = 0; j < N; j++) {
now[j] = (pre[j] >> iv) | tab[j];
}
dfs(d+1,now,len+iv);
}
}
}
void preJudge(int n)
{
SZ = 0;
for(int iv = 1; iv <= n; iv++){
bool ok = true;
for(int i = 0; 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+1];
while(~scanf("%d",&n)&&n) {
memset(tab,0,sizeof(tab));
for(int i = 0; i < N; i++){
scanf("%s",G);
for(int j = 0; j < n; j++) if(G[j] == 'X'){
tab[i] |= 1<<j;
}
}
ans = n*10;
preJudge(n);
dfs(1,tab,n);
printf("%d\n",ans);
}
return 0;
}
原文链接: https://www.cnblogs.com/jerryRey/p/4645651.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/219119
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!