ABC175D-solution

igAC · 2023-10-27 15:50:48 · 题解

\text{Description}

洛谷 link

ATlink

简要题意（atcoder better）：

高桥将用一枚棋子在编号为 1, 2, \cdots, N 的数组方格上下棋。方格 i 上写着一个整数 C_i。

此外，他还得到了一个 1, 2, \cdots, N 的排列组合：P_1, P_2, \cdots, P_N。

现在，他将选择一个方格并将棋子放在该方格上。然后，他将在 1 和 K 之间（包括 1 和 K）下若干次棋：

• 在一步棋中，如果棋子现在在 i 位 (1 \leq i \leq N)，将其移动到 P_i 位置。在这里，他的得分会增加 C_{P_i}。

帮助他找出对局结束时的最大可能得分。(游戏开始时的得分是 0）。

\text{Solution}

简单题。

如果你把它当作一个图论来做的话，你会发现每个点的入度和出度都是 1，那么整个图是由若干个简单环构成的。

然后就可以枚举起始点，接着枚举在哪个点结束，计算答案即可。

时间复杂度 O(n^2)。

具体实现可参考代码。

\text{Code}

#include<bits/stdc++.h>
#define LLINF -1e18
#define int long long
#define N 5005
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void print(int x){
    if(x<0) putchar('-'),x=~(x-1);
    if(x>9) print(x/10);
    putchar(x%10+48);
}
int n,k,to[N],a[N];
int ans=-LLINF;
signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;++i) to[i]=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i){//枚举起始点
        int j=i,sum=0;
        vector<int>vec;
        while(true){
            j=to[j],sum+=a[j];
            vec.push_back(sum);
            if(j==i) break;
        }//找环
        int cirsize=vec.size();
        for(int s=0;s<vec.size() && s<k;++s){//枚举在哪个点停下
            int cnt=(k-s-1)/cirsize;
            if(sum<=0) ans=max(ans,vec[s]);
            else ans=max(ans,vec[s]+cnt*sum);
        }
    }
    printf("%lld",ans);
    return 0;
}