Longest Simple Cycle
题意
有 n条链，第 i条链上有c[i] 个点，a[i] 为第 i ii 条链的顶点与第i−1 条链的连接点，b[i] 为第i条链的最后一个点与第i−1 条链的连接点。
找这样的一个环，环上的每个点都只被访问一次，问该环的最大长度为多少。
思路
反向遍历c[i]
设res1 和res2
res1 表示 每条链 a[i] 和b[i] 之间的点的个数 定义为 向内
res2 表示 每条链a[i] 和b[i] 到两个端点的点的个数 定义为 向外
当 a [ i ] ≠ b [ i ]时 ：
显然可知res1 需要用res2 来更新 即只有右边那条链选择向两个端点 这条链才能选择向内
res1 = res2 + abs(a[i] - b[i]) + 1;
当 i=2 时a[i] 和 b[i] 表示第2条链连在第一条链的位置 显然不能取向外的 因为这样形成不了环 只能取向内的情况
所以有
else { res2 += 1; maxn = max(maxn, res2); if (i != 2)res2 = c[i - 1]; }
需要注意的是：
if (res2 < c[i - 1] && i != 2) res2 = c[i - 1];
可以把还未形成的环看成两部分 一部分是res2 表示的上一条链取向外操作下的 “环” (此时还未形成环) 一部分(左半边)还未形成 右边的环对左边未找到的环的大小无影响 当res2<c[i−1] 时显然把 第i−1 条链全部当作环的右半部分更优
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 100010; LL a[N], b[N], c[N]; void solve() { int n; cin >> 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]); LL res1 = 0; //向内 LL res2 = 0; //向外 LL maxn = -INF; res1 = c[n], res2 = c[n]; for (int i = n; i >= 2; --i) { if (a[i] != b[i]) { res1 = res2 + abs(a[i] - b[i]) + 1; if (i != 2) res2 += c[i - 1] - abs(a[i] - b[i]) - 1 + 2; else res2 = res1; maxn = max(maxn, max(res1, res2)); if (res2 < c[i - 1] && i != 2) res2 = c[i - 1]; } else { res2 += 1; maxn = max(maxn, res2); if (i != 2)res2 = c[i - 1]; } } cout << maxn << endl; } int main() { int t; cin >> t; while (t--) solve(); return 0; }
