2020蓝桥杯大赛软件类省赛第二场 Java 大学 B 组 子串分值和

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

对于一个字符串 S，我们定义 S 的分值 f(S ) 为 S 中出现的不同的字符个数。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。现在给定一个字符串 S [0…n − 1]（长度为 n），请你计算对于所有 S 的非空
子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是多少。 【输入格式】

输入一行包含一个由小写字母组成的字符串 S。 【输出格式】

输出一个整数表示答案。 【样例输入】

ababc 【样例输出】

28 【样例说明】

对于 20% 的评测用例，1 ≤ n ≤ 10；对于 40% 的评测用例，1 ≤ n ≤ 100；对于 50% 的评测用例，1 ≤ n ≤ 1000；对于 60% 的评测用例，1 ≤ n ≤ 10000；对于所有评测用例，1 ≤ n ≤ 100000。 思路

使用动态规划定义一个一维数组dp，dp[i]：表示以当前字符结尾f(0…i)+f(1…i)…f(i)的和再定义一个一维数组pre[26]，pre[i]：表示当前字符上一次出现的位置。找到状态转移方程： dp[i] = dp[i-1] + i - 1 - pre[s.charAt(i)-97] + 1;最后求出，所有的dp[i]，把dp[i]全部相加，就是本题答案。 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		int n = str.length();
		long[] dp = new long[n];
		long res = 0;
		dp[0] = 1;
		res += dp[0];
		int[] pre = new int[26];
		Arrays.fill(pre, -1);
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				pre[str.charAt(i)-97] = i;
			} else {
				if (pre[str.charAt(i)-97] == -1) {
					//代表当前位置字符前面都没有重复
                    //每位都在之前的位置上加1
                    //再加上当前新增这一位的字串
					dp[i] = dp[i-1] + i - 1 - 0 + 1 + 1;
					pre[str.charAt(i)-97] = i;
					res += dp[i];
				} else {
					//把当前字符前面没有重复的都加1,一共有（i - 1 - index）个
                    //再加上当前新增这一位的字符串
					int index = pre[str.charAt(i)-97];
					dp[i] = dp[i - 1] + i - 1 - index + 1;
					pre[str.charAt(i)-97] = i;
					res += dp[i];
				}
			}
		}
		System.out.println(res);
	}
}