【鏈接】 我是鏈接,點我呀:)
【題意】

給你一個序列.
你可以選擇起點i。
然后每次往右跳k次。
得到下一個值a[i+k];。
問你跳m次能得到的最大值ma是多少。
如果>=s輸出0
否則輸出s-ma;

【題解】

最后肯定會形成gcd(n,k)個環的。
對于每個環(長度為cnt。
預處理出從1..2cnt的前綴和C[2*cnt](當成鏈處理就好
枚舉它從起點i開始。
然后考慮它會怎么走?
1.如果c[cnt]>0,temp1加上m/cntC[cnt],然后對于剩余的m%cnt次走的機會。
求出c[i-1..i+m%cnt-1]這一段的最大值get_ma,減去c[i-1]就是剩余的m%cnt次能走出來的最大值了。即temp1+=get_ma-c[i-1];
temp = max(temp,temp1)
2.如果m>=cnt,那么還有一種可能,就是剩余的最后一圈留著不走完整圈,而只取一個最大的值,這個時候
如果c[cnt]>0,temp2+=(m/cnt - 1)*C[cnt],然后我們還留了一圈,也即cnt次機會可以走
則求出c[i-1..i+cnt-1]這一段的最大值get_ma2,然后再減去c[i-1]就是剩余的cnt次能走出來的最大值了,即temp2+=get_ma2-C[i-1]
temp = max(temp,tepm1)
對于每個起點i。都求出temp1,tepm2
最后return temp
就是當前這個環上走m次能得到的最大值了。
枚舉所有的環取最大的temp就是答案了

【代碼】

#include <bits/stdc++.h> #define LL long long using namespace std;const int N = 1e4; const int M = 15;int n,m,k; LL s; int a[N+10],b[N*2+10],cnt; LL c[N*2+10],mi[N*2+10][M+5]; int vis[N+10];LL get_ma(int l,int r){int len = r-l+1;len = log2(len);return max(mi[l][len],mi[r-(1<<len)+1][len]); }LL ok(){c[0] = 0;for (int i = 1;i <= cnt;i++)c[i] = b[i],c[i+cnt] = b[i];for (int i = 1;i <= 2*cnt;i++) c[i]+=c[i-1];for (int i = 0;i <= 2*cnt;i++) mi[i][0] = c[i];for (int L = 1;L<=M;L++)for (int i = 0;i <= 2*cnt;i++){if (i+(1<<L)-1>2*cnt) break;mi[i][L] = max(mi[i][L-1],mi[i+(1<<(L-1))][L-1]);}LL temp = 0;for (int i = 1;i <= cnt;i++){LL temp1 = 0;//第一種情況.//如果環的和大于0就盡量用if (c[cnt]>0) temp1 += 1LL*m/cnt*c[cnt];int rest = m%cnt;if (rest>0) temp1+=get_ma(i-1,i+rest-1)-c[i-1];LL temp2 = 0;//第二種情況//留cnt個if (m>=cnt){if (c[cnt]>0) temp2 += 1LL*(m-cnt)/cnt*c[cnt];temp2+=get_ma(i-1,i+cnt-1)-c[i-1];}temp = max(temp,temp1);temp = max(temp,temp2);}return temp; }int main() {//freopen("D:\\rush.txt","r",stdin);ios::sync_with_stdio(0),cin.tie(0);int T;cin >> T;int kk = 0;while (T--){cin >> n >> s >> m >> k;for (int i = 1;i <= n;i++) cin >> a[i];for (int i = 1;i <= n;i++) vis[i] = 0;LL ans = 0;for (int i = 1;i <= n;i++)if (vis[i]==0){cnt = 0;for (int j = i;vis[j]==0;j = (j+k)>n?(j+k-n):j+k){cnt++;b[cnt] = a[j];vis[j] = 1;}ans = max(ans,ok());}cout<<"Case #"<<++kk<<": ";if (s<ans)cout<<0<<endl;elsecout<<s-ans<<endl;}return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/9698652.html

總結

以上是生活随笔為你收集整理的【hdu 6444】Neko's loop的全部內容，希望文章能夠幫你解決所遇到的問題。

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