題目

題目鏈接

題解及代碼

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5+7; int f[2*N][55],a[2*N],sum[2*N],ans[2*N],pb[2*N]; int T,n,k; #define pr(x) cout<<#x<<":"<<x<<endl /** 題解* 由于最多跳一個(gè)環(huán)就結(jié)束，因此倍長(zhǎng)數(shù)組就足夠了。* 預(yù)處理出f[i][j]表示從i點(diǎn)出發(fā)，每次跳j步，最遠(yuǎn)能跳到哪里。* 預(yù)處理出sum[i]表示數(shù)組[1,i]位置中有多少個(gè)'#'。* 預(yù)處理出pb[i]，表示i位置前面距離最近的'#'的位置。* ans數(shù)組為存儲(chǔ)最終答案的數(shù)組。* 枚舉出發(fā)點(diǎn)i，再?gòu)拇蟮叫∶杜e跳躍長(zhǎng)度m，很容易得到f[i][m]得到下一個(gè)點(diǎn)nxt，* 如果nxt不為0，則表示可以走，為了避免多跳，我們把nxt和pb[i]+1取一個(gè)最小值，* 然后ans[i] += ceil((nxt-now)/m);* 并更新now = nxt;* 這樣的話，總的時(shí)間復(fù)雜度就是O(nk)*/ int main(){freopen("jumps.in","r",stdin);cin>>T;while(T--){cin>>n>>k;memset(f,0,sizeof(f));memset(sum,0,sizeof(sum));memset(a,0,sizeof(a));memset(ans,0,sizeof(ans));for(int i = 1;i <= n;++i){char c;scanf(" %c",&c);if(c == '#') a[i] = 1;sum[i] = sum[i-1] + a[i];}for(int i = n+1;i <= 2*n;++i){a[i] = a[i-n];sum[i] = sum[i-1] + a[i];}sum[2*n+1] = sum[2*n];int pre = 0;for(int i = 1;i <= 2*n;++i){if(a[i]) pre = i;else pb[i] = pre;}for(int i = 2*n;i;--i) for(int m = k;m;--m){if(a[i]) continue;int t = m + i;if(t > 2*n){if(!a[t-2*n] && sum[2*n]-sum[i]+sum[t-2*n] <= 1)f[i][m] = 2*n+1;}else{if(!a[t] && sum[t]-sum[i] <= 1)f[i][m] = max(f[t][m],t);}}for(int i = 1;i <= n;++i){if(a[i]) continue;int it = i;for(int m = k;m;--m){int nxt = f[it][m];if(nxt) {if(nxt > pb[i+n]) nxt = pb[i+n]+1;ans[i] += (nxt-it) / m;if((nxt-it)%m) ans[i]++;it = nxt;}if(it > pb[i+n]) break;}if(it < pb[i+n]) ans[i] = -1;}for(int i = 1;i <= n;++i){if(i != 1) cout<<' ';cout<<ans[i];}cout<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2017 ACM Jordanian Collegiate J.Efficiency Test 动态规划、类倍增的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。