题解：P5154 数列游戏

DevilsFlame · 2024-10-23 13:03:03 · 题解

一眼典型区间 dp。

关于擦除和得分，我们难想到动归式子：f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j])。可是难点就在于擦除条件。于是草草写下这行代码：

if((i + 1 == j || p[i + 1][j - 1]) && check(a[i],a[j]))
{
    p[i][j] = 1;
    f[i][j] = f[i + 1][j - 1] + b[i] + b[j];
    continue;
}

不难发现，这漏了情况。这里主要难的就是擦除条件。
可是，也是有单调性。f[i][i + 1] 是可以确定的，那么 f[i][i + 2] = max(f[i][i + 1],f[i + 1][i + 2])，但这是奇数的情况。那如果是 f[1][4]？

满足可以让 f[1][4] 完全擦除的有 2 种情况：

1. f[1][2] && f[3][4]
2. f[2][3] && gcd(a[1],a[4]) != 1
   一旦完全擦除，那么这一区间肯定就是最大值。 可以用 bool 数组判断区间是否完全擦除。

   #include<bits/stdc++.h>
   #define N 805
   using namespace std;
   long long n,a[N],b[N],f[N][N];
   bool g[N][N];//判断该区间是否可擦除 
   int gcd(int a,int b)
   {
   if(b == 0) return a;
   return gcd(b,a % b);
   }
   inline bool check(int a,int b)//是否满足提议要求
   {
   if(gcd(a,b) == 1) return 0;
   return 1;
   }
   int main()
   {
   ios::sync_with_stdio(0);
   cin.tie(0),cout.tie(0);
   cin >> n;
   for(int i = 1;i <= n;i ++) cin >> a[i];
   for(int i = 1;i <= n;i ++) cin >> b[i];
   for(int t = 1;t < n;t ++)//枚举长度(t + 1)
       for(int i = 1;i + t <= n;i ++)//区间左端点
       {
           int j = i + t;//右端点 = i + t
           if(check(a[i],a[j]) && (i + 1 == j || g[i + 1][j - 1]))
           //如果(j - i + 1)是奇数，那么 g[i + 1][j - 1] 肯定为 0 
           {
               g[i][j] = 1;
               f[i][j] = f[i + 1][j - 1] + b[i] + b[j];
               continue;
           }
           for(int k = i;k < j;k ++)//枚举界点
           {
               f[i][j] = max(f[i][k] + f[k + 1][j],f[i][j]);
               if(g[i][k] && g[k + 1][j])//该区间可擦除（分段擦除，例如 2 4 9 15）
               {
                   g[i][j] = 1;
                   break;
               }
           }
       }
   cout << f[1][n] << endl;
   return 0;
   }

   该算法不是最优，但很简单易懂，时间复杂度为 O(n^3)。