题目

洛谷

做法

考虑一整个子串可完全消除\(can[i][j]\)，是有两种方法转移的：
\((can[i+1][j-1]),(can[i][k],can[k+1][j])\longrightarrow can[i][j]\)

\(dp[i][j]\)表区间\((i,j)\)能得到的最大分数
这个转移可以利用\(can\)特判，具体跟上面一样

My complete code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=1001;
LL n;
LL dp[maxn][maxn],sum[maxn],A[maxn],B[maxn];
bool can[maxn][maxn];
int main(){
    cin>>n;
    for(LL i=1;i<=n;++i) cin>>A[i];
    for(LL i=1;i<=n;++i) cin>>B[i],sum[i]=sum[i-1]+B[i];
    for(LL i=1;i<n;++i) can[i][i+1]=(__gcd(A[i],A[i+1])!=1);
    for(LL len=4 ;len<=n;len+=2)
        for(LL l=1,r=len;r<=n;++l,++r){
            can[l][r]|=can[l+1][r-1] & (__gcd(A[l],A[r])!=1);
            for(LL k=l;k<r;++k)
                can[l][r]|=can[l][k] & can[k+1][r];
        }
    for(LL len=2;len<=n;++len){
        for(LL l=1,r=len;r<=n;++l,++r){
            if(can[l][r]) dp[l][r]=sum[r]-sum[l-1];
            for(LL k=l;k<r;++k)
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
        }
    }cout<<dp[1][n];
    return 0;
}

数列游戏

原文：https://www.cnblogs.com/y2823774827y/p/10422655.html