hdu 5900 区间dp

题意：给你n对pair 里面有两个值，分别是key 和 val 。你可以取相邻的两个pair 获得其中的val，前提是两个pair 的key 的 gcd 不为 1。当然你把相邻的两个取走了之后原本不相邻的两个就变得相邻了。比如：你将下标为 2，3 取走之后，下标1,4就变得相邻了，求你可以获得的最大val。

题解：典型的合并问题，应该能想到用区间dp，但这里得考虑清楚，状态怎么转移。我们定义dp[i][j]为i~j能够获取的最大值。那么怎么更新状态呢，我们用一个前缀和去维护val，如果

dp[i+1][j-1]能够取完，其值一定为sum[j-1]-sum[i]。如果当前的区间i,j互质，那么i~j都可以取完。否则我们就要考虑剩下哪些val能够使最终的结果最大，这里就用for循环去跑一遍，枚举中间值k,看剩下哪些值是最优解。

（对区间dp的构造有了更深的理解过几天可以写一篇小结了）。

ac代码：

    #include <cstdio>

    #include <iostream>

    #include <cstring>

    #define mt(a) memset(a,0,sizeof(a))

    using namespace std;

    typedef long long ll;

    ll key[];

    ll v[];

    ll dp[][];

    ll sum[];

    ll gcd(ll a,ll b)

    {

        if(b==) return a;

        return gcd(b,a%b);

    }

    int main()

    {

        int t;

        scanf("%d",&t);

        while(t--)

        {

            int n;

            mt(dp);

            mt(sum);

            scanf("%d",&n);

            for(int i=;i<=n;i++)

            {

                scanf("%lld",&key[i]);

            }

            for(int i=;i<=n;i++)

            {

                scanf("%lld",&v[i]);

                sum[i]=sum[i-]+v[i];

            }

            for(int l=;l<=n;l++)

            {

                for(int i=;i+l-<=n;i++)

                {

                    int j=i+l-;

                    if(dp[i+][j-]==(sum[j-]-sum[i]) && gcd(key[i],key[j])!=)

                    {

                        dp[i][j]=sum[j]-sum[i-];

                        continue;

                    }

                    for(int k=i;k<j;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]);

                }

            }

            //

            printf("%lld\n",dp[][n]);

        }

    }

巴特西

hdu 5900 区间dp

最新文章

热门文章