正題

題目大意:https://www.luogu.org/problemnew/show/P3575

---

題目大意

一個環，上面有若干個點，若干個詢問$x$。
表示上一個降落點和下一個降落點距離不能超過$x$，然后求至少要降落多少次(起點可以任意)

---

解題思路

首先明顯環形$dp$，然后斷環成鏈，復制一份放到后面，預處理距離前綴和數組$sum$。
然后考慮貪心設$las{t}_i$數組，定義$d{p}_i$表示$las{t}_i～i(i>n)$這段范圍的降落次數，然后優先飛最遠。也就是$j$是$i$的最前的降落地點。因為$j$滿足單調性，所以就可以$O(n)$的預處理出來(或者在$dp$的時候處理)。然后首先顯然
$$d{p}_i=d{p}_j+1$$
然后因為計算上了$d{p}_j$，所以要從$las{t}_j$開始也就是
$$las{t}_i=las{t}_j$$
然后當$i?las{t}_i>=n$時就是答案了。

---

$code$

#include<cstdio> #include<algorithm> #define ll long long using namespace std; const ll N=2000100; ll n,t,imp; ll sum[N],dp[N],last[N]; void get_answer(ll l){if(l<imp){printf("NIE\n");return;}for(ll i=n+1,j=1;i<=2*n;i++){while(sum[i]-sum[j]>l) j++;dp[i]=dp[j]+1;last[i]=last[j];if(i-last[i]>=n){printf("%lld\n",dp[i]);return;}} } int main() {scanf("%lld%lld",&n,&t);for(ll i=1;i<=n;i++){last[i]=i;scanf("%lld",&sum[i]);imp=max(imp,sum[i]);sum[i+n]=sum[i];sum[i]+=sum[i-1];}for(ll i=n+1;i<=2*n;i++)sum[i]+=sum[i-1];for(ll i=1;i<=t;i++){ll l;scanf("%lld",&l);get_answer(l);} }

總結

以上是生活随笔為你收集整理的P3575-[POI2014]DOO-Around the world【环形dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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