507「LibreOJ NOI Round #1」接竹竿-DP

小编 2026-07-13 阅读:1141 评论:0

https://loj.ac/problem/507 题目：取出一段区间的要求是这段区间的两个端点是一样的，所以我们可以考虑用类似于链式前向星的方法，储存相同端点的到达。考虑定一个一维的状态，...

https://loj.ac/problem/507
题目：取出一段区间的要求是这段区间的两个端点是一样的，所以我们可以考虑用类似于链式前向星的方法，
储存相同端点的到达。考虑定一个一维的状态，一维的状态始终是十分好定的：
DP[I]表示前II张扑克处理后能够得到的最大得分，转移方程：
对于第i张照片，有可以取出计分与不去出计分两种情况。
不取出计分：dp[ i ]=dp [ i - 1 ];
若第i张照片要取出计分，考虑计分的方式：
与它前面的已经形成的区间合并成一个大的区间：dp [ head [ i ]] + sum [ i ] - sum [ head [ i ] ]

与它前面的那个相同花色的形成一个区间取走： dp [ head [ i ] -1 ]+sum [ i ] - sum [ head [ i ] - 1 ]

#include<bits/stdc++.h>
using namespace std;
#define maxn 1234567
#define ll long long
ll n,k,sum[maxn],v[maxn];
ll dp[maxn],head[maxn],d;
ll last[maxn];
int main()
{
    scanf(\"%lld%lld\",&n,&k);
    for(int i=1; i<=n; i++)
    {
        scanf(\"%lld\",&v[i]);
        head[i]=last[v[i]];
        last[v[i]]=i;
    }
    for(int i=1; i<=n; i++)
    {
        scanf(\"%lld\",&d);
        sum[i]=sum[i-1]+d;
    }
    for(int i=1; i<=n; i++)
    {
        dp[ i ]=dp [ i - 1 ];
        if(head[i])
            dp[i]=max(dp[i],max(dp[head[i]-1]+sum[i]-sum[head[i]-1],dp[head[i]]+sum[i]-sum[head[i]]));
    }
    printf(\"%lld\\n\",dp[n]);
    return 0;
}