【NHOI2018】扑克游戏

【问题描述】
有一种别样“小猫钓鱼”扑克游戏。有 N 张牌，每张牌都有一个花色和点数。游戏的规则：扑克接龙时，若前面有同样花色的牌，你可以将这两张牌连同之间的牌都取走，得到的分值为取走牌点数之和。这里说的是可以，不是必须。给定扑克接龙的顺序，求最多的得分。
【输入格式】
第一行一个整数 N。
第二行 N 个整数，依次表示 1～N 张牌的花色。
第三行 N 个整数，依次表示 1～N 张牌的点数。
【输出格式】
一个整数，为游戏可以得到最大得分。
【输入样例】
7
1 2 1 2 3 2 3
1 4 3 4 3 4 5
【输出样例】
23
数据范围：1<=n<=3000
【解题思路】
简单的DP+利用前缀和求出数据中某一段的和。
【参考程序】

#include<iostream>

#include<cstdio>

using namespace std;

int n,c[3001],f[3001],dp[3001];

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d",&c[i]);

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

    {

        scanf("%d",&f[i]);

        f[i]=f[i-1]+f[i];

    }

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

    {

        dp[i]=dp[i-1];

        for (int j=1;j<i;j++)

            if (c[i]==c[j])

                dp[i]=max(dp[i],dp[j-1]+f[i]-f[j-1]);

    }

    cout<<dp[n];

    return 0;

}

巴特西

【NHOI2018】扑克游戏

最新文章

热门文章