題目鏈接
題目大意：給定一個長度為n的字串，每個位置代表一個bug，然后給定m個補丁，每個補丁有兩個字串，第一個是初始序列（‘0’表示bug是否存在都無所謂，‘+’表示必須存在，‘-’表示必須不存在），第二個是打上補丁后的序列（‘0’表示不變，‘-’表示不存在bug，‘+’表示存在bug）初始時你的序列是存在所有bug的序列，每個補丁都有一個花費時間，問通過打上補丁消除所有bug所需的最小時間，
分析：通過手動模擬樣例就能大概理解題意，我們可以把當前序列看成一種狀態，用一個n為二進制數或長度為n的陣列來表示，這里選擇用二進制數表示，每個補丁可以看成一種決策，每個狀態最多可以有m種決策，所以問題就是從全是bug的狀態到無bug的狀態的最短距離，可以注意到這個狀態圖是存在環的，所以不可以使用動態規劃，而且狀態圖中每條邊的邊權也不全為1，所以不可以單純使用bfs去搜索，考慮最短路演算法，dijkstra和bellman_ford，都可以使用，這里的狀態總數高達
2
n
2^n
2n個，所以dijkstra要加堆優化，bellman_ford要加佇列優化，最后輸出答案即可，
#include<bits/stdc++.h>
#define PII pair<int,int>
#define MAIN main
using namespace std;
typedef char st[10];
const int inf=0x3f3f3f3f;
const int N=1e2+10;
struct node
{
int dis,st;
bool operator < (const node &a)const
{
return dis>a.dis;
}
};
int n,m;
int w[N],vis[(1<<22)],dis[(1<<22)];
char s[N][N],t[N][N];
bool judge(int st,int i)
{
for(int j=0;j<n;j++)
{
if(s[i][j]=='0') continue;
if(s[i][j]=='+'&&!(st&(1<<j))) return false;
else if(s[i][j]=='-'&&(st&(1<<j))) return false;
}
return true;
}
void update(node u,node &v,int i)
{
v.st=u.st;
for(int j=0;j<n;j++)
{
if(t[i][j]=='0') continue;
if(t[i][j]=='+'){
v.st|=(1<<j);
}
else if(t[i][j]=='-'){
v.st&=(~(1<<j));
}
}
}
void bfs()
{
memset(vis,0,sizeof(vis));
for(int i=0;i<(1<<n);i++) dis[i]=inf;
dis[(1<<n)-1]=0;
priority_queue<node>q;
node now;
now.dis=0;
now.st=(1<<n)-1;
q.push(now);
while(!q.empty())
{
node u=q.top();q.pop();
if(vis[u.st]) continue;
vis[u.st]=1;
for(int i=1;i<=m;i++)
{
if(judge(u.st,i))
{
node v;
update(u,v,i);
if(dis[v.st]>dis[u.st]+w[i]){
dis[v.st]=dis[u.st]+w[i];
v.dis=dis[v.st];
q.push(v);
}
}
}
}
if(dis[0]!=inf) printf("Fastest sequence takes %d seconds.\n",dis[0]);
else printf("Bugs cannot be fixed.\n");
}
int MAIN()
{
int tt=0;
while(scanf("%d%d",&n,&m)==2)
{
if(n==0&&m==0) break;
for(int i=1;i<=m;i++)
{
scanf("%d",&w[i]);
scanf("%s",s[i]);
scanf("%s",t[i]);
}
printf("Product %d\n",++tt);
bfs();
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260325.html
標籤：其他
上一篇：洛谷P1664 每日打卡心情好