C. Bear and Colors 区间枚举的技巧

http://codeforces.com/problemset/problem/673/C

先说一个枚举区间的技巧，枚举前缀，不要枚举后缀。

就是下面这个代码是不好的

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            区间[j, i]
        }
    }

为什么呢？就是很多东西重复了，而且也被迫用不上。只能老老实实地计算。

但如果考虑下枚举前缀。

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            区间[i, j]
        }
    }

则能用上以前的东西

比如[1, 1] ---> [1, 2]（这个时候只是新加了一个元素，相对应上面的枚举后缀是减去一个元素，但是减去，题目会变得很混乱，比如1、2、2、1，减去一个1，[3, 4]的答案是2）。但是如果是增加一个元素的话，那么我只需要用最优值去比较即可。

就是从[1, i]转移到[1, i + 1]，只需要用[1, i]的最优值的个数去和新加入后的a[i + 1]的个数进行比较即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 5000 + 20;
int a[maxn];
int book[maxn];
int ans[maxn];
void work() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        int best = a[i];
        book[best]++;
        ans[best]++;
        for (int j = i + 1; j <= n; ++j) {
            book[a[j]]++;
            if (book[best] < book[a[j]]) {
                ans[a[j]]++;
                best = a[j];
            } else if (book[best] == book[a[j]] && best > a[j]) {
                best = a[j];
                ans[a[j]]++;
            } else {
                ans[best]++;
            }
        }
        memset(book, 0, sizeof book);
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d ", ans[i]);
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code

个人感觉有点dp的感觉，只不过枚举的时候要有技巧