区间价值 --- 题解--动态规划
目录
区间价值
题目描述
输入描述:
输出描述:
输入
输出
备注:
思路：
代码：
区间价值
J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com)
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
对于一个数组a，定义其价值是其中不同的数的个数，比如对于数组[3,2,2,3,1]，价值就是3。对于一个给定的长度len，求出所有长度为lenlenlen的子区间的价值之和是对于吉吉国王来说很重要，现在吉吉国王会告诉你他想知道的长度lenlenlen，你需要告诉吉吉国王答案。
比如数组[3,2,2,3,1]，长度为2的子区间有[3,2],[2,2],[2,3],[3,1]，那么价值分别是2,1,2,2，因此这个数组长度为2的价值和就是7。
输入描述:
第一行一个n表示数组的长度。
第二行n个数，第iii个数表示ai。
第三行一个q表示询问的次数。
接下来q行，每行一个整数表示查询的长度。
输出描述:
输出q行，第i行表示第i个询问的答案。
示例1
输入
5 3 2 4 3 1 4 1 2 3 4
输出
5 8 9 7
备注:
1≤n≤1e6
思路：
这道题容易想到的是暴力解法（区间dp）但这肯定是会爆时间的。
现在设dp[i] 表示区间为i时的价值和。
那怎么从dp[i-1] 转移到 dp[i]
假如 当前区间为3， 数组为 32441
324 -> 3244 贡献不变
244 -> 2441 贡献加1
441 -> null 贡献-2
这里可以看出从dp[i-1] 到 dp[i] 会损伤掉后面 i-1个数的贡献值，并且前几个区间有s[i]的贡献增加。
前几个区间中那些区间是会提供贡献，或者说那些数在区间变大时可以提供贡献，这是可以预处理出来的，因为可以观察发现只有两个相同数的相隔距离大于等于i时，他们才会在长度为i的区间中提供一个贡献。（这里需要用一个后缀和统计）
代码：
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex7* @author:HWJ* @Data: 2023/12/5 19:53*/
public class Main {static int maxN = (int) 1e6 + 5;public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] arr = new int[maxN];int[] last = new int[maxN];long[] s = new long[maxN];int[] diff = new int[maxN];int[] cnt = new int[maxN];for (int i = 1; i <= n; i++) {arr[i] = input.nextInt();s[i - last[arr[i]]]++;last[arr[i]] = i;}for(int i = n; i > 0; i--){s[i] = s[i] + s[i + 1];}int tot = 0;for(int i = n; i > 0; i--){if (++cnt[arr[i]] == 1) tot++;diff[n - i + 1] = tot;}long[] ans = new long[n + 1];ans[1] = n;for(int i = 2; i <= n; i++){ans[i] = ans[i - 1] + s[i] - diff[i - 1];}int q = input.nextInt();for (int i = 0; i < q; i++) {int a = input.nextInt();System.out.println(ans[a]);}}
}