叙述一个网站的建设过程,wordpress知名网站,新乡哪个公司做网站好,wordpress 上传中文文件【链接】 我是链接,点我呀:) 【题意】 给你一个序列. 你可以选择起点i。 然后每次往右跳k次。 得到下一个值a[ik];。 问你跳m次能得到的最大值ma是多少。 如果s输出0 否则输出s-ma; 【题解】 最后肯定会形成gcd(n,k)个环的。 对于每个环(长度为cnt。 预处理出从1..2cnt的… 【链接】 我是链接,点我呀:) 【题意】 给你一个序列. 你可以选择起点i。 然后每次往右跳k次。 得到下一个值a[ik];。 问你跳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..im%cnt-1]这一段的最大值get_ma,减去c[i-1]就是剩余的m%cnt次能走出来的最大值了。即temp1get_ma-c[i-1]; temp max(temp,temp1) 2.如果mcnt,那么还有一种可能,就是剩余的最后一圈留着不走完整圈,而只取一个最大的值,这个时候 如果c[cnt]0,temp2(m/cnt - 1)*C[cnt],然后我们还留了一圈,也即cnt次机会可以走 则求出c[i-1..icnt-1]这一段的最大值get_ma2,然后再减去c[i-1]就是剩余的cnt次能走出来的最大值了,即temp2get_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[N10],b[N*210],cnt;
LL c[N*210],mi[N*210][M5];
int vis[N10];LL get_ma(int l,int r){int len r-l1;len log2(len);return max(mi[l][len],mi[r-(1len)1][len]);
}LL ok(){c[0] 0;for (int i 1;i cnt;i)c[i] b[i],c[icnt] 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;LM;L)for (int i 0;i 2*cnt;i){if (i(1L)-12*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 (rest0) temp1get_ma(i-1,irest-1)-c[i-1];LL temp2 0;//第二种情况//留cnt个if (mcnt){if (c[cnt]0) temp2 1LL*(m-cnt)/cnt*c[cnt];temp2get_ma(i-1,icnt-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 (jk)n?(jk-n):jk){cnt;b[cnt] a[j];vis[j] 1;}ans max(ans,ok());}coutCase #kk: ;if (sans)cout0endl;elsecouts-ansendl;}return 0;
}转载于:https://www.cnblogs.com/AWCXV/p/9698652.html
