1. 首页
2. 区间DP
3. 本页

HDU 5900 QSC and Master (区间dp)

题目链接：点我~~

题意：$n$ 个pair<int , int>，每次可以选相邻两个pair。如果他们的first不互质就可以把它们都删掉，并且获得second之和的分数，问最大得分。

思路：设f[i][j]为[i,j]这段区间能取得的最大得分，转移就是不取左边/不取右边/断开拼起来/取两边，其中取两边需要中间能取干净才能取。复杂度 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 100100;

PI a[310];
LL dp[310][310];
LL sum[310];

void solve(int n)
{
    memset(dp,0,sizeof(dp));
    for(int len=1; len<n; ++len)
    {
        for(int i=1; i+len<=n; ++i)
        {
            int j=len+i;
            for(int k=1; k<j; ++k)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
            if(__gcd(a[i].first,a[j].first)>1)
            {
                if (j==i) dp[i][j]=max(dp[i][j],(LL)a[i].second+a[j].second);
                else if (dp[i+1][j-1]==sum[j-1]-sum[i])
                    dp[i][j]=max(dp[i][j],dp[i+1][j-1]+a[i].second+a[j].second);
            }
        }
    }
    printf("%lld\n",dp[1][n]);
}

int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; ++i)
            scanf("%d",&a[i].first);
        sum[0]=0;
        for(int i=1; i<=n; ++i)
        {
            scanf("%d",&a[i].second);
            sum[i]=sum[i-1]+a[i].second;
        }
        solve(n);
    }
    return 0;
}