qbxt DAY4 T4
吐槽:除了爆搜没有别的部分分做法,极其不友好
暴力肯定是枚举选择哪一个数,换种思路可以想想有一个队列,每次加一个数的过程
首先一个显然的结论是前k个数一定是一个好数,要不然会有浪费的数
拿样例(k=4)举个例子:
现在有好数(1 1 1 1),当我们加入一个新数(2)的时候,其实最前面的(1)已经没有用了,因为我们只需要知道后(k)位数,那么当前的数就变成了(1 1 1 2),相当于走了一条边
这样相当于所有好数组成一个哈密顿通路(从一个点出发经过其他所有点的路径)
求出两两好数之间最短距离,然后状压dp求出哈密顿通路
8位1-4组成的数可以看作4进制数进行运算,从而节省空间
int trans(int x)//4进制
{
int y = 0;
for(int i = 0; i < k; i ++)
{
y |= (x % 10 - 1) << (2 * i);
x /= 10;
}
return y;
}
可以用最短路算法,但是在边权只有4的时候,可以拆边使用bfs求最短路
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, k;
int good[25], bad[10005];
int dis[N][4];
bool vis[N];
int trans(int x)//4进制
{
int y = 0;
for(int i = 0; i < k; i ++)
{
y |= (x % 10 - 1) << (2 * i);
x /= 10;
}
return y;
}
queue<pair<int, int> > q;
void bfs(int x)
{
memset(dis, 0x3f ,sizeof(dis));
if(vis[x]) return;
dis[x][0] = 0;
q.push(make_pair(x, 0));
while(!q.empty())
{
int u = q.front().first, v = q.front().second;
q.pop();
int now = dis[u][v];
if(v)
{
if(dis[u][v - 1] > 1e9)
{
dis[u][v - 1] = now + 1;
q.push(make_pair(u, v - 1));
}
continue;
}
for(int i = 1; i <= 4; i ++)
{
int y = ((u << 2) | (i - 1)) & ((1 << (2 * k)) - 1);
if(dis[y][i - 1] > 1e9 && !vis[y])
{
dis[y][i - 1] = now + 1;
q.push(make_pair(y, i - 1));
}
}
}
}
int dist[25][25];
int f[21][1 << 20];
int calc(int x)
{
int y = 0;
for(int i = 0; i < k; i ++)
{
y += x % 10;
x /= 10;
}
return y;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++)
scanf("%d", &good[i]);
for(int i = 1; i <= m; i ++)
{
scanf("%d", &bad[i]);
vis[trans(bad[i])] = 1;
}
for(int i = 1; i <= n; i ++)
{
bfs(trans(good[i]));
for(int j = 1; j <= n; j ++)
{
dist[i][j] = dis[trans(good[j])][0];
}
}
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; i ++)
f[i][1 << (i - 1)] = calc(good[i]);
for(int S=0;S<(1<<n);S++)
for(int i=1;i<=n;i++)
if((S&(1<<(i-1))))
{
for(int j=1;j<=n;j++)
if(!(S&(1<<(j-1))))
f[j][S|(1<<(j-1))]=min(f[j][S|(1<<(j-1))],f[i][S]+dist[i][j]);
}
int ans=1e9;
for(int i=1;i<=n;i++)
ans=min(ans,f[i][(1<<n)-1]);
printf("%d
",ans);
}