本文共 1804 字，大约阅读时间需要 6 分钟。

AtCoder Beginner Contest 175 D.Moving Piece

• 若 $k<=len$，很简单，取最大前缀和即可~
• 若 $k>len$，我们要仔细考虑，此时如果前缀和 $sum[len]\le 0$，那么我们取的循环节越多答案无疑越小，所以只需要取最大前缀和即可，也即和第一种情况一样；如果前缀和 $sum[len]>0$，此时我们发现循环节取得越多答案就越大，最多取的个数无疑是 $num=\lfloor \frac{k}{len}\rfloor$，那么就相当于选一个 $k\%len$ 里的最大前缀和加上前面 $num$ 个前缀和的和，即 a n s = m a x { s u m [ k % l e n ] } + n u m ∗ s u m [ l e n ] ans=max\lbrace sum[k\%len]\rbrace+num*sum[len] ans=max{
  sum[k%len]}+num∗sum[len]此处有个小细节，就是当 $k\%len=0$ 时，我们个数要减 $1$，空一个循环节出来，以便和上面的取余统一，其实答案并没有变化，简便写法而已~

反正是挺考验思维的，好题b（￣▽￣）d　，AC代码如下:

#include
   
    using namespace std;typedef long long ll;const int N=5e3+5;int n;ll k,a[N],p[N],cnt[N]={
   0},sum[N][N]={
   0};ll dfs(ll i){
       ll u=i,num=1,pos=1;    while(p[i]!=u){
           num++;        i=p[i];        sum[u][pos]=sum[u][pos-1]+a[i];      pos++;    }    sum[u][pos]=sum[u][pos-1]+a[u];    return num;}int main(){
       cin>>n>>k;    for(int i=1;i<=n;i++) cin>>p[i];    for(int i=1;i<=n;i++) cin>>a[i];    ll ans=-1e18;    for(int i=1;i<=n;i++){
           cnt[i]=dfs(i);        ll mx1=-1e18,mx2=-1e18;        for(int j=1;j<=cnt[i];j++){
               mx1=max(mx1,sum[i][j]);        }        for(int j=1;j<=(k%cnt[i]?k%cnt[i]:cnt[i]);j++){
               mx2=max(mx2,sum[i][j]);        }        if(k>cnt[i]){
               ll num=(k%cnt[i])?k/cnt[i]:k/cnt[i]-1;            ans=max(ans,max(mx1,num*sum[i][cnt[i]]+mx2));        }        else ans=max(ans,mx2);    }    cout<
   

转载地址：https://zaizai.blog.csdn.net/article/details/108150410 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！