题目描述

状态机DP或线性DP

状态机DP

import java.util.*;

public class Main{
    static int N = 1000010;
    static int[][] f = new int[N][2];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        for(int i = 1; i <= s.length(); i ++){
            f[i][0] = Math.max(f[i-1][0],f[i-1][1]);
            f[i][1] = f[i-1][0] + s.charAt(i-1) - 'a' + 1;
        }

        System.out.println(Math.max(f[s.length()][0],f[s.length()][1]));

    }
}

线性DP

import java.util.*;

public class Main{
    static int N = 1000010;
    static int[] f = new int[N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        f[1] = s.charAt(0) - 'a' + 1;
        for(int i = 2; i <= s.length(); i ++){
            f[i] = Math.max(f[i - 1], f[i - 2] + s.charAt(i - 1) - 'a' + 1);
        }

        System.out.println(f[s.length()]);

    }
}