Longest Simple Cycle(CF1476C)(线性dp)

题意：
有 (n) 条链，第 (i) 条链上有 (c_{i}) 个点，从第 (2) 条链开始，第 (i) 条链的首尾和第 (i-1) 条链的 (a[i]) 点、 (b[i]) 点相连接。问能构成的最大环的长度为多少。

---

想法：

• 简单线性dp。
• (dp[i]) 表示加上第 (i) 条边后的最大环的长度。
• 显然 (dp) 方程为
  当 (a[i]==b[i])时， (dp[i]=c[i]+1)
  当 (a[i]!=b[i])时， (dp[i]=c[i]+max(dp[i-1]+abs(a[i]-b[i])-1,abs(a[i]-b[i])+1))

---

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int maxn=100005;

ll a[maxn],b[maxn],c[maxn];
ll dp[maxn];
int main()
{
    int T,n;
    cin>>T;
    while(T--){
        memset(dp,0,sizeof dp);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)scanf("%lld",&b[i]);

        dp[1]=0;
        ll ans=0;
        for(int i=2;i<=n;i++){
            if(a[i]==b[i]){
                dp[i]=c[i]+1;
            }else{
                ll num=abs(a[i]-b[i]);
                dp[i]=c[i]+max(dp[i-1]-(num-1),num+1);
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }   
    return 0; 
}