題意

平面上有n個點。初始有V的權值，每次可以從一個點走到與他距離不超過V的點，當V>0時也可以讓V/2且到達任意一個點。問從每個點出發能否遍歷所有點。
n,V<=200000

分析

顯然只有O(logV)O(logV)種不同的步數。
當權值VV被固定后，整條鏈被分成若干個區間，每個區間內的點可以互達。
把每一種VV對應的所有區間求出來后，不難發現兩個區間要么是相離關系，要么是包含關系。
從某個點出發能否遍歷所有點，就相當于把該點能通過權值VV到達的點去掉，問能否用除了VV以外的權值對應的區間去覆蓋整條線段。
這個可以狀壓dp：
設f[S]f[S]表示用SS里面的權值從左往右覆蓋數軸，最大能到達的右端點。
g[S]g[S]表示最小能到達的左端點。
然后答案就很好求了。

代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define MAX(x,y) x=max(x,y) #define MIN(x,y) x=min(x,y) #define inf 0x3f3f3f3f using namespace std;const int N=400005;int n,v,g[N*2],f[N*2],bin[25],tot,len[25],lef[25][N],rig[25][N],a[N],bel[N],p1[N],p2[N]; bool ans[N];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=x*10+ch-'0';ch=getchar();}return x*f; }void dp() {bin[0]=1;for (int i=1;i<=tot;i++) bin[i]=bin[i-1]*2;for (int i=0;i<bin[tot];i++) g[i]=n+1;for (int i=0;i<bin[tot];i++)for (int j=0;j<=tot;j++)if (!(i&bin[j])) MAX(f[i+bin[j]],rig[j][f[i]+1]),MIN(g[i+bin[j]],lef[j][g[i]-1]);for (int i=0;i<bin[tot];i++){int l=f[i],r=g[i^(bin[tot]-1)];if (l+1>=r){for (int j=1;j<=n;j++) ans[j]=1;return;}if (p1[bel[l+1]]<=l+1&&p2[bel[l+1]]>=r-1) ans[bel[l+1]]=1;} }int main() {n=read();v=read();for (int i=1;i<=n;i++) a[i]=read();tot=0;len[0]=0;while (v) len[++tot]=v,v>>=1;sort(len,len+tot+1);memset(lef,inf,sizeof(lef));for (int i=0;i<tot;i++)for (int j=1;j<=n;j++){int l=j;while (l<n&&a[l+1]-a[l]<=len[i]) l++;rig[i][j]=l;lef[i][l]=j;j=l;}int id=0;for (int j=1;j<=n;j++){int l=j;bel[j]=++id;while (l<n&&a[l+1]-a[l]<=len[tot]) l++,bel[l]=id;p1[id]=j;p2[id]=l;j=l;}dp();for (int i=1;i<=n;i++) puts(ans[bel[i]]?"Possible":"Impossible");return 0; }

總結

以上是生活随笔為你收集整理的AtCoder Grand Contest 012 E - Camel and Oases 状压dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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