这道题TLE了n次,不过A了之后反而不觉得难了。
把head作为对于每一个元素,往前能够达到最长的合法区间的最前端,则不难理解,head该如何选取。
有两种情况:
1.当前元素在前面出现过,则head就是上一次出现过的位置后的一个和head本身比较后的较大者;
2.当前元素没出现过,则head是最近一次出现过的被重复过的元素了。
那么为什么对于每一个元素,ans += i - head + 1呢?
是这样的,对于第i个元素,向前搜,则可选的方法,又不与后面选取结果重复的话,则是:
head ~ i, head+1 ~ i,head+2 ~ i,……,i;
一共i - head + 1种。
AC代码:
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int MAXN = 100001; bool v[MAXN]; int s[MAXN]; int wall[MAXN]; int i, j, k; int N; int head; __int64 ans; int main() { #ifdef BellWind freopen("B.in", "r", stdin); #endif // BellWind while (~scanf("%d", &N)) { ans = 0; head = 1; memset(v, 0, sizeof(v)); for (i = 1; i <= N; i++) { scanf("%d", &wall[i]); if (v[wall[i]]) {head = max(head, s[wall[i]] + 1);} ans += i - head + 1; s[wall[i]] = i; v[wall[i]] = true; } printf("%I64d\n", ans); } return 0; }