题意：给定一个整数串，有Q组询问，问这个串中长度为w的子串中不同的数字之和为多少，这题的动态规划感觉很有技巧性。
解法：设f[i]表示w为 i 时不同的数字之和，那么考虑f[i+1]和f[i]的关系可以得知：f[i+1]就是从f[i]中去除最后一个子串后在每个串后加上一个数字的情况，因此可以得到这样的一个递推式：f[i] = f[i-1] - tail[N-i+2] + left 其中tail[N-i+2]表示长度为i-1的最后一个子串中不同的数字共有多少个，left表示所有数字中与前一个相同数字的长度大于 i 的数字还剩多少个。因此还要另外预处理出后缀不相同数字个数，和最近相同数字的长度，注意如果一个数字只出现一次的话，那么考虑到统计域的问题，应该将其视为长度为x，x为该元素的下标。本来这题是打算减掉那些长度小于 i 的值，但是由于无法考虑到一个元素的统计域问题，一直调不出来。
代码如下：
#include#include #include #include #include using namespace std;const int MaxN = 1000005;typedef long long LL;int N, seq[MaxN];int cnt[MaxN];LL f[MaxN];int L[MaxN];int tail[MaxN];char vis[MaxN];// L[i]记录数字i出现的当前最靠右的位置// cnt[i]记录相同数字相邻距离为i的数字的个数// tail[i]记录从后往前，即i到N的不同的数的数量void init() { memset(L, 0xff, sizeof (L)); memset(cnt, 0, sizeof (cnt)); memset(vis, 0, sizeof (vis)); tail[N+1] = 0; for (int i = 1; i <= N; ++i) { if (!(~L[seq[i]])) { L[seq[i]] = i; ++cnt[i]; } else { ++cnt[i-L[seq[i]]]; L[seq[i]] = i; } } for (int i = N; i >= 1; --i) { tail[i] = tail[i+1]; if (!vis[seq[i]]) { vis[seq[i]] = 1; ++tail[i]; } } int left = N; for (int i = 1; i <= N; ++i) { left -= cnt[i-1]; f[i] = f[i-1] - tail[N-i+2] + sum; }}int main() { int Q, x; while (scanf("%d", &N), N) { for (int i = 1; i <= N; ++i) { scanf("%d", &seq[i]); } init(); scanf("%d", &Q); while (Q--) { scanf("%d", &x); printf("%I64d\n", f[x]); } } return 0; }