前言

很容易的就發現了只有log次跳躍。
然后狀壓DP。
似乎就是個簡單題吧（怎么比12c還簡單）

題意

一排點，兩點間有距離。
初始你有一個行走值v，如果相鄰兩點距離不超過v你可以自由在這兩點行走。
當v大于0時，你可以選擇某一時刻突然飛到任意點，這樣做后v會減半（下取整）。
問從每個位置初始出發能否到達所有位置。

DP

預處理left[i,j]表示在i行走值已經減半j次能往左走到哪，同理有right。
我們每次從i點出發，用行走值v可以走到[l,r]。
那么你需要將接下來的行走值分成兩部分然后覆蓋[1,l-1]和[r+1,n]。
我們希望預處理一個mi[i]表示用行走值中的一部分覆蓋[1,i]，另一部分能覆蓋[x,n]，x的最小值是多少。
然后為了這個先狀壓DP一下，設f[s]表示用s集合里的行走值覆蓋[1,x]最大的x是多少，每次可以枚舉一個不在s里的i然后轉移，用這個i去覆蓋接下來一段。
同理會有個g[s]表示覆蓋[x,n]。
于是接下來再枚舉拿哪些覆蓋前綴即可處理mi。

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; const int maxn=200000+10,lgn=20; int f[maxn*5],g[maxn*5],mi[maxn],left[maxn][lgn+10],right[maxn][lgn+10],v[lgn+10],x[maxn]; int i,j,k,l,r,s,t,n,m,tot,top; int main(){ scanf("%d%d",&n,&t); fo(i,1,n) scanf("%d",&x[i]); v[0]=t; t/=2; while (t){ v[++top]=t; t/=2; } v[++top]=0; reverse(v,v+top+1); fo(j,0,top){ left[1][j]=1; fo(i,2,n) if (x[i]-x[i-1]<=v[j]) left[i][j]=left[i-1][j];else left[i][j]=i; right[n][j]=n; fd(i,n-1,1) if (x[i+1]-x[i]<=v[j]) right[i][j]=right[i+1][j];else right[i][j]=i; } f[0]=0; g[0]=n+1; fo(s,1,(1<<(top+1))-1){ f[s]=0; g[s]=n+1; fo(i,0,top) if (s&(1<<i)){ r=s^(1<<i); if (f[r]==n) f[s]=n; else f[s]=max(f[s],right[f[r]+1][i]); if (g[r]==1) g[s]=1; else g[s]=min(g[s],left[g[r]-1][i]); } } fo(i,0,n) mi[i]=n+2; fo(i,0,(1<<top)-1){ r=((1<<top)-1)^i; mi[f[i]]=min(mi[f[i]],g[r]); } fd(i,n-1,0) mi[i]=min(mi[i],mi[i+1]); fo(i,1,n){ l=left[i][top];r=right[i][top]; if (mi[l-1]<=r+1) printf("Possible\n");else printf("Impossible\n"); } }

總結

以上是生活随笔為你收集整理的[agc012e]Camel and Oases的全部內容，希望文章能夠幫你解決所遇到的問題。

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