题目链接：https://loj.ac/problem/507

题目描述

一天，神犇和 LCR 在玩扑克牌。他们玩的是一种叫做“接竹竿”的游戏。

游戏规则是：一共有张牌，每张牌上有一个花色和一个点数，花色不超过种。将这些牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌花色相同的牌，你可以选择将这张牌和任意一张花色相同的牌之间的所有牌全部取出队列（包括这两张牌本身），并得到与取出的所有牌点数和相同的分数。现在已知 LCR 把这张牌放入队列的顺序，求她最多能得多少分。

输入顺序即为 LCR 放入队列的顺序。即，表示第张放入的牌的花色，表示第张放入的牌的点数。

请注意，如果你知道类似的纸牌游戏，请尤其仔细地阅读规则，以免因为理解题意错误而出现不必要的问题。

输入格式

第一行两个整数。
第二行，个整数表示花色，满足。
第三行，个整数表示点数。

输出格式

输出一行一个整数，表示最多能得到的分数。

样例

样例输入 1

7 3
1 2 1 2 3 2 3
1 2 1 2 3 2 3

样例输出 1

样例解释 1

第 1 步，向队列加入。现在的队列：
第 2 步，向队列加入。现在的队列：
第 3 步，向队列加入。现在的队列：
第 4 步，向队列加入，取出。现在的队列：
第 5 步，向队列加入。现在的队列：
第 6 步，向队列加入。现在的队列：
第 7 步，向队列加入，取出。现在的队列：

样例输入 2

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

样例输出 2

思路：这是一道区间dp题，状态转移方程挺容易想的： dp[i]=max(dp[i-1],s[i]+lst[c[i]]);但有一个坑点就是时间给的很少，如果不用快读，在输入时就爆了

代码：

#include <bits/stdc++.h>

#define MAX 1000005

using namespace std;

long long read() {//快读模板，这道题不用快读铁T(可能是学习oj的原因- _ -!)

    long long x = 0, f = 1;

    char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (isdigit(ch)) {

        x = x * 10 + ch - '0';

        ch = getchar();

    }

    return x * f;

}

long long n,k,s[MAX],dp[MAX],lst[MAX],c[MAX];

int main()

{

    n=read();

k=read();

    memset(lst,128,sizeof(lst));

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

c[i]=read();

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

s[i]=s[i-1]+read();

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

{

        dp[i]=max(dp[i-1],s[i]+lst[c[i]]);//状态转移方程

        lst[c[i]]=max(lst[c[i]],dp[i-1]-s[i-1]);//lst用来记录每个点可以加上的值

    }

    cout<<dp[n];

}

问题 J: 接竹竿

题目链接：https://loj.ac/problem/507