Educational Codeforces Round 103 (Rated for Div. 2)C.Longest Simple Cycle

題目大意

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100010],b[100010],c[100010],sum[100010];//sum數組用來儲存每一時刻的最長長度
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
    {
      scanf("%lld",&c[i]);
      c[i]--;
    }
    for(int i = 1;i <= n; i++)
    {
      scanf("%lld",&a[i]);
    }
    for(int i = 1;i <= n; i++)
    {
      scanf("%lld",&b[i]);
    }
    long long maxx = 0;//maxx用來記錄周遊過程中環的最大值
    for(int i = 2;i <= n; i++)
    {
      if(b[i] == a[i])
      {
        sum[i] = c[i]+2;//當bi與ai重合時，其必為圓的出發點。
      }
      else if(b[i]!=a[i]&&i>2)//當bi與ai不重合時，此時要判斷它應該作為新的起點還是圓環的中間部分
      {
        if(abs(a[i] - b[i]) > sum[i - 1] - abs(a[i] - b[i]))//若目前線上ai與bi的距離大于上一圓環的長度，則重新計算圓環
        {
          sum[i] = abs(a[i] - b[i]) + 2 + c[i];
        }
        else
        {
          sum[i] = sum[i-1] - abs(b[i] - a[i]) + 2 + c[i];//反之将其作為上一圓環的一部分
        }
      }
      else if(b[i]!=a[i]&&i==2)//這裡是特判i=2時的情況，此時必為起點
      {
        sum[i]=abs(b[i]-a[i])+c[i]+2;
      }
      maxx=max(maxx,sum[i]);//每次記錄長度的最大值
    }
    printf("%lld\n",maxx);
    for(int i=1;i<=n;i++)
    {
      a[i]=b[i]=c[i]=sum[i]=0;//清空各數組
    }
  }
}