HDU 4455 Substrings（dp+预处理）

题意：给定一个整数串，有Q组询问，问这个串中长度为W的子串中不同的数字个数之和为多少。

题解：dp+预处理

$dp[i]$：长度为$i$子串中不同数字个数之和。

对于1 1 2 3 4 4 5，我们先假设w为2： 可得子串为【1 1】【1 2】【2 3】【3 4】【4 4】【4 5】

若w为3： 可得子串为【1 1 2】【1 2 3】【2 3 4】【3 4 4】【4 4 5】

我们发现，w=3相当于w=2的前5个子串往后扩充一位，并将w=2的最后一个子串删除，那么我们可得递推方程：$dp[i]=dp[i-1]+len[i]-f[i-1]$。 $len[i]$：相同数间隔长度 ≥ $i$的数的个数，表示扩充的那一位。 $f[i]$：w为$i$，最后一个区间不同数字个数。

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long using namespace std; const int maxn = 1e6 + 5; int n, q, w, pre[maxn], len[maxn], a[maxn], vis[maxn], f[maxn]; ll dp[maxn]; int main() { while (~scanf("%d", &n) && n) { memset(len, 0, sizeof(len)); memset(pre, 0, sizeof(pre)); memset(vis, 0, sizeof(vis)); memset(f, 0, sizeof(f)); //记录后i个数有几个不同的数 for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); len[i - pre[a[i]]]++; pre[a[i]] = i; //记录前一个a[i] } for (int i = n - 1; i >= 1; i--) len[i] += len[i + 1]; //长度≥i的个数 for (int i = 1; i <= n; i++) { f[i] = f[i - 1]; if (!vis[a[n - i + 1]]) { vis[a[n - i + 1]] = 1; f[i]++; } } dp[0] = 0; for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + len[i] - f[i - 1]; scanf("%d", &q); while (q--) { scanf("%d", &w); printf("%lld\n", dp[w]); } } return 0; }