HDOJ 5900 QSC and Master 【2016沈阳网赛】区间DP

题意：有N对数值排成一列，一个是KEY值，一个是VALUE值

如果相邻的KEY值不是互斥的（最大公约数不为1），那么我们就可以把它们消掉，得到的分数就是他们的VALUE值的和

同时，因为这两个值消去了，那么原来不相邻的数就可以相邻了

区间DP还是比较明显的

一方面是因为n小，n最大为300，符合n<1000的区间DP的要求

另一方面是对数值的操作，我们必须知道相邻的数值的情况，才会知道大区间的情况

这个题的坑点在于：

我们需要设计两个数组来搞

dp【i】【j】：从i点到j点的区间【i，j】的最大的VALUE值

ok【i】【j】：从i点到j点的区间【i，j】是不是可以全部被删除

我一开始只有一个dp【i】【j】的数组，所以怎么着都是错的

dp【i】【j】=-1，作为未访问的节点

dp【i】【j】=0，我是定义为，该区间是已经访问过的，但是不能消去的区间

但是，这样会有问题！

因为，大区间中可能有多个不能合并的能够消去的小区间

这时候小区间的值dp【i】【j】>0，那么在dp转移的时候，大区间就有了值，但是它是不可以全局合并的

这就想到了要搞两个数组

然后就是区间dp的经典转移了

要么，x和y单独出来可能匹配，让【x+1，y-1】成为一个区间

要么，在中间枚举一个k，让【x，k】，【k+1】【y】成为两个区间

代码就很好实现了，用记忆化去写

#include<bits/stdc++.h>
using namespace std;

const int maxn=400;
#define LL __int64

int t,n;
LL a[maxn],b[maxn];
LL dp[maxn][maxn];
bool ok[maxn][maxn];
LL gcd[maxn][maxn];

LL getdp(int x,int y){
    if (dp[x][y]!=-1) return dp[x][y];
    if (x>=y) return dp[x][y]=0;
    if (x+1==y){
        if(gcd[x][y]>1){
            ok[x][y]=true;
            return dp[x][y]=b[x]+b[y];
        }
        return dp[x][y]=0;
    }
    LL res=getdp(x+1,y-1);
    if (gcd[x][y]>1&&ok[x+1][y-1]){
        res+=b[x]+b[y];
        ok[x][y]=true;
    }
    LL aa,bb;
    for(int k=x;k<y;k++){
        aa=getdp(x,k);
        bb=getdp(k+1,y);
        if (ok[x][k]&&ok[k+1][y]) ok[x][y]=true;
        res=max(aa+bb,res);
    }
    return dp[x][y]=res;
}

int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%I64d",&b[i]);
        for(int i=1;i<n;i++)
            for(int j=i+1;j<=n;j++)
                gcd[i][j]=__gcd(a[i],a[j]);
        memset(dp,-1,sizeof(dp));
        memset(ok,false,sizeof(ok));
        /*
        for(int i=1;i<n;i++)
            if (__gcd(a[i],a[i+1])>1)
                ok[i][i+1]=true;
        for(int i=1;i<=n;i++)
        for(int len=3;len<=n;len++){
            int j=i+len-1;
            if (j>n) continue;
            for(int k=i+1;k<j;k++)
                if (ok[i][k]&&ok[k+1][j]) ok[i][j]=true;
            if (dp[i+1][j-1]&&__gcd(a[i],a[j])>1) ok[i][j]=true;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                printf("%d%c",ok[i][j],j==n?'\n':' ');
        */
        printf("%I64d\n",getdp(1,n));
        //for(int i=1;i<=n;i++)
          //  for(int j=1;j<=n;j++)
            //    printf("%d%c",ok[i][j],j==n?'\n':' ');
        //for(int i=1;i<=n;i++)
          //  for(int j=1;j<=n;j++)
            //    printf("%I64d%c",dp[i][j],j==n?'\n':' ');
    }
    return 0;
}

10
6 6 5 5 7 5 3 5 7 7
2 3 4 5 6 7 8 9 10 11
11
7 6 6 5 5 7 5 3 5 7 7
1 2 3 4 5 6 7 8 9 10 11

可以用我的程序打个表，就知道什么思想了