Atcoder Beginner Contest 345 --- E - Colorful Subsequence --- 题解 ---- （很好的dp题）

E - Colorful Subsequence:

题目大意：

思路解析：

这道题很容易可以看出是一道dp题，可以设计出dp状态为 dp[i][j][k]代表当前在第i个球，已经删除了j个球，并且当前删除j个球后最右边的球的颜色为k。因为颜色 C<=N，那么整个dp的转移时间复杂度为 O(N * N * K)超时

观察这个状态的转移过程 如果当前球的颜色为 k， 那么dp[i][j][k] = max( dp[i-1][j][f] ) + V (f != k) ,如果当前球的颜色不为k，dp[i][j][k] = dp[i-1][j-1][k]. 可以发现整个状态转移方程中只有两个有用的转移信息， dp[i-1][j-1][k], dp[i-1][j][max]  还可以发现他们的颜色一定不同，即对于每个球，每种删除情况我们只需要记录两个信息，即删除j个球后能达到的最佳情况和此佳情况，因为后续转移也之后通过这两个情况转移。

那么我们可以将 状态设计为 dp[i][j][k] 表示删除了i个球， j==0表示最佳情况，j==1表示此佳情况，k==0表示此情况最右边的球的颜色，k==1表示此情况的最佳价值。

 for (int i = 0; i < n; i++) {
            long c = f.nextInt();
            long v = f.nextLong();
            for (int j = k; j >= 1; j--) {
                if (dp[j][0][0] != c){ // 如果颜色不同，那么可以将这个球加在右边，
                    dp[j][0][0] = c;
                    dp[j][0][1] += v;
                }else { // 如果颜色相同，因为最佳情况和此佳情况的颜色一定不同，所以可以将球加在此佳情况的右边，并将此情况作为最佳情况
                    dp[j][0][1] = dp[j][1][1] + v;
                }
                dp[j][1][0] = -1;
                dp[j][1][1] = -inf;
                // 看删除 j-1个球时在删除这个球，变为删除j个球后，有没有比当前答案优秀的
                for (int l = 0; l < 2; l++) {
                    if (dp[j-1][l][1] >= dp[j][0][1]){
                        if (dp[j-1][l][0] != dp[j][0][0]){ // 如果两个情况的颜色，那么可以将曾经的最佳情况作为当前的此佳情况
                            dp[j][1][0] = dp[j][0][0];
                            dp[j][1][1] = dp[j][0][1];
                        }
                        dp[j][0][0] = dp[j-1][l][0];
                        dp[j][0][1] = dp[j-1][l][1];
                    }// 如果这个情况能替换掉此佳情况， 就让它替换掉此佳情况
                    else if (dp[j-1][l][1] >= dp[j][1][1] && dp[j-1][l][0] != dp[j][0][0]) {
                        dp[j][1][0] = dp[j-1][l][0];
                        dp[j][1][1] = dp[j-1][l][1];
                    }
                }

            }
            // 这是一个球都不删除的情况
            if (c != dp[0][0][0]){
                dp[0][0][0] = c;
                dp[0][0][1] += v;
            }else { // 如果出现连续球，就必须得删除球
                dp[0][0][1] = -inf;
            }
        }

代码实现：

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static long inf = (long) 2e18;

    public static void main(String[] args) throws IOException {
        int n = f.nextInt();
        int k = f.nextInt();
        long[][][] dp = new long[k+1][2][2];
        for (int i = 0; i < k + 1; i++) {
            for (int j = 0; j < 2; j++) {
                dp[i][j][0]=-1; dp[i][j][1] = -inf;
            }
        }
        dp[0][0][0] = 0; dp[0][0][1] = 0;
        for (int i = 0; i < n; i++) {
            long c = f.nextInt();
            long v = f.nextLong();
            for (int j = k; j >= 1; j--) {
                if (dp[j][0][0] != c){ // 如果颜色不同，那么可以将这个球加在右边，
                    dp[j][0][0] = c;
                    dp[j][0][1] += v;
                }else { // 如果颜色相同，因为最佳情况和此佳情况的颜色一定不同，所以可以将球加在此佳情况的右边，并将此情况作为最佳情况
                    dp[j][0][1] = dp[j][1][1] + v;
                }
                dp[j][1][0] = -1;
                dp[j][1][1] = -inf;
                // 看删除 j-1个球时在删除这个球，变为删除j个球后，有没有比当前答案优秀的
                for (int l = 0; l < 2; l++) {
                    if (dp[j-1][l][1] >= dp[j][0][1]){
                        if (dp[j-1][l][0] != dp[j][0][0]){ // 如果两个情况的颜色，那么可以将曾经的最佳情况作为当前的此佳情况
                            dp[j][1][0] = dp[j][0][0];
                            dp[j][1][1] = dp[j][0][1];
                        }
                        dp[j][0][0] = dp[j-1][l][0];
                        dp[j][0][1] = dp[j-1][l][1];
                    }// 如果这个情况能替换掉此佳情况， 就让它替换掉此佳情况
                    else if (dp[j-1][l][1] >= dp[j][1][1] && dp[j-1][l][0] != dp[j][0][0]) {
                        dp[j][1][0] = dp[j-1][l][0];
                        dp[j][1][1] = dp[j-1][l][1];
                    }
                }

            }
            // 这是一个球都不删除的情况
            if (c != dp[0][0][0]){
                dp[0][0][0] = c;
                dp[0][0][1] += v;
            }else { // 如果出现连续球，就必须得删除球
                dp[0][0][1] = -inf;
            }
        }
        dp[k][0][1] = Math.max(-1, dp[k][0][1]);
        w.println(dp[k][0][1]);
        w.flush();
        w.close();
        br.close();
    }


    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}