P5154 数列游戏

· · 题解

区间DP加求GCD。

（本片题解用更相减损法来求GCD）。

设f[l][r]为bool类型,表能否取走l位置到r位置的数。

然后转移方程分两种情况。

①取走l位置与r位置的数（前提：a[l]与a[r]不互质） 。

这就必须保证f[l+1][r-1]为true（能被取走）！

于是此方程式便能推导出来f[l][r]|=f[l+1][r-1]。

②取走i位置与i+1位置的数（前提：a[i]与a[i+1]不互质，l<i<r-1）。

这就必须保证f[l][i]与f[i+1][r]为true（能被取走）！

于是此方程式便能推导出来f[l][r]|=f[l][j]*f[j+1][r];

接下来两种做法（注：记得搞前缀和）。

①线性DP也就是俺代码用的方法（跟那些跳桩子的题差不多）。

②DFS（就像走路那样比如f[l][r]为l可以走到r）。

至于更相减损法，比辗转相除法更优，不过此题貌似不需要。

还有就是l~r中的数的个数一定是双数！（解释i+=2）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[1000001];
bool f[1001][1001];
long long b[1000001],s[1000001],ans[1000001];
long long Max(long long AA,long long BB){
    if(AA>BB) return AA;
    return BB;
}
int gcd(int A,int B){//更相减损法 
    if(B>A){
        int TURN=A;
        A=B;
        B=TURN;
    }
    if(A==B) return A;
    if(A%2==0&&B%2==0) return 2*gcd(A/2,B/2);
    if(A%2!=0&&B%2==0) return gcd(A,B/2);
    if(A%2==0&&B%2!=0) return gcd(A/2,B);
    return gcd(A-B,B);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        s[i]=s[i-1]+b[i];
    }
    for(int i=1;i<=n-1;i++){
        if(gcd(a[i],a[i+1])!=1) f[i][i+1]=true;
        else f[i][i+1]=false;
    }
    for(int i=3;i<=n;i+=2){
        for(int l=1;l<=n-i;l++){
            int r=l+i;
            if(gcd(a[l],a[r])!=1)  f[l][r]|=f[l+1][r-1];
            for(int j=l+1;j<r-1;j++) f[l][r]|=f[l][j]*f[j+1][r];
        }
    }
    for(int i=2;i<=n;i++){
        ans[i]=ans[i-1];
        for(int j=1;j<i;j++){
            if(f[j][i]==false) continue;
            ans[i]=Max(ans[i],ans[j-1]+s[i]-s[j-1]);
        }
    }
    printf("%lld",ans[n]);
}