区间价值 --- 题解--动态规划

目录

区间价值

题目描述

输入描述:

输出描述:

输入

输出

备注:

思路：

代码：

---

 

区间价值

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]);}}
}