Time Limit: 10 Sec Memory Limit: 128 MB

Description

xx作為信息學界的大神，擁有眾多的粉絲。為了感謝眾粉絲的愛戴，xx決定舉辦一場晚會。為了氣派，xx租了一個巨大的燈屏，這個燈屏有\(m\)行，每行有\(n\)個小燈泡。對于每一行燈，有L種操作方法，第i種表示你能將任意長度恰為\(A_i\)的連續一段燈泡的狀態取反（滅變亮，亮變滅）。現對于每一行給定\(K\)個點，要求這K個點發光，其余點必須保持熄滅狀態。求每一行達到目標狀態的最小操作數。

Input

第一行一個數\(m\)，表示LED屏的行數。

對于LED屏的每一行：

第一行為\(n,k,L\)，意義見上。

第二行為\(k\)個數，表示要求發光的\(k\)個點。

第三行為\(L\)個數，表示\(L\)種操作方式。

Output

對于LED屏的每一行：如果無法達到目標狀態，輸出\(-1\)，否則輸出最少次數。

Sample Input

2 10 8 2 1 2 3 5 6 7 8 9 3 5 3 2 1 1 2 3

Sample Output

2 -1

HINT

對于\(100\%\)的數據，\(T\leq 10\)，\(N\leq 10000\)，\(K\leq 10\),\(L\leq 100\),\(1\leq A_i\leq N\)。

Source

By zjwst960422

Solution

一個很神仙的思路。

發現\(N\)非常大，但是\(K\)非常小，顯然是狀壓DP，但是只狀壓\(K\)又不太好辦。

于是我們發現，原來序列里只會有\(2K\)個點是一段\(0\)與一段\(1\)的間隔的點（我們這里取前一段的最后一個點）。然后我們又發現，不斷地對一個段序列取反，實際上是讓這一段和等長的只有\(1\)的序列異或。而這樣之后，取反的區間內，相鄰兩個點的相對狀態不會改變，即相鄰兩個點是否相等是不會改變的。

因此，我們對原序列\(a_i\)做一個這樣的處理，維護這個點與后一個點的異或查分：

\[b[i]=a[i]\ xor\ a[i+1]\quad 0\leq i \leq n\]

這樣的話，我們對\(a\)里面連續的一段(\(l..r\))取反，只會改變\(b\)里面的\(b[l-1]\)與\(b[r]\)兩個點。

同時,\(a\)數組與\(b\)數組之間的又是唯一確定的關系。所以我們要\(A\)的末狀態，等價于對應的\(B\)。

然后我們發現，如果把全\(0\)作為初狀態，發光后的作為末狀態，這樣末狀態太亂了，不方便轉移。倒不如，倒過來，發光后的為初，全\(0\)為末。然后\(A\)全\(0\)，對應的\(B\)也是全\(0\)的。

我們發現，我們實際上只是需要把初始的\(B\)里面的所有\(1\)全部去掉即可。然后，如果兩個點坐標差恰好為一個操作時，就可以操作一次，那就是把這兩點取反，中間的點不變！。那么我們要算出只取反\(i\)和\(j\) 需要的操作次數\(f[i][j]\)，其實只需要從\(i\)出發跑BFS最短路即可。

然后考慮如何求出總的操作次數。

我們發現，\(B\)數列中最多有\(2K\) 個點為\(1\)，所以我們只應該把那\(2K\)個點取反，其他點都不能動。那么我們狀壓一下這些點。然后就是一個非常顯而易見的DP。\(dp[S]\)表示\(S\)里面的點已經完成了取反的任務。

\[dp[S]=\min\{dp[C_S{i,j}]+f[i][j]\ \ |\ \ i,j\in S\}\qquad dp[0]=0\]

然后我們類似于憤怒的小鳥的優化，這里會產生很多重復的轉移，我們的\(i\)只需要取\(S\)中的最小的點就可以了。

最后答案為\(dp[full\_set]\)。

時間復雜度\(O(nmk+2^kk)\)

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #define inf 1000000000 #define N 10005 #define M 2000005 #define T 45 using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}return x*f; } int n,K,m,cnt; int x[N],size[N],a[N],num[N]; bool vis[N],mark[M]; int dis[N],d[25][25]; int q[N]; int f[M]; void bfs(int x) {memset(vis,0,sizeof(vis));int t=0,w=1;dis[x]=0;q[t]=x;vis[x]=1;while(t!=w){int now=q[t];t++;for(int i=1;i<=m;i++){if(now+size[i]<=n&&(!vis[now+size[i]])){vis[now+size[i]]=1;dis[now+size[i]]=dis[now]+1;q[w++]=now+size[i];}if(now-size[i]>0&&(!vis[now-size[i]])){vis[now-size[i]]=1;dis[now-size[i]]=dis[now]+1;q[w++]=now-size[i];}}}for(int i=1;i<=n;i++)if(num[i]){if(!vis[i])d[num[x]][num[i]]=inf;else d[num[x]][num[i]]=dis[i];} } int dp(int x) {if(!x)return 0;if(mark[x])return f[x];mark[x]=1;f[x]=inf;int st=0;for(int i=1;i<=cnt;i++){if(x&(1<<(i-1))){if(!st)st=i;else{if(d[st][i]!=inf)f[x]=min(f[x],dp(x^(1<<(st-1))^(1<<(i-1)))+d[st][i]);}}}return f[x]; } int main() {freopen("password.in","r",stdin);freopen("password.out","w",stdout);n=read();K=read();m=read();for(int i=1;i<=K;i++){x[i]=read();a[x[i]]=1;}for(int i=1;i<=m;i++)size[i]=read();for(int i=n+1;i;i--)a[i]^=a[i-1];n++;for(int i=1;i<=n;i++)if(a[i])num[i]=++cnt;for(int i=1;i<=n;i++)if(a[i])bfs(i);dp((1<<cnt)-1);if(f[(1<<cnt)-1]==inf)printf("-1");else printf("%d",f[(1<<cnt)-1]);return 0; }

轉載于:https://www.cnblogs.com/hankeke/p/BZOJ3508.html

總結

以上是生活随笔為你收集整理的BZOJ3508 开灯 [校内NOIP2018模拟20181027] 密码锁的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。