题目描述

In the good old days, Farmer John served a boring cuisine comprising but a single type of cow food to his N (1 <= N <= 40000) prize dairy cows. Times change. Today he serves the herd a total of M (1 <= M <= N) different types of food (conveniently numbered 1..M).
The cows are picky. Cow i has a single food preference Pi (1 <= Pi <= M) and will eat only that favorite food.
Each day at feeding time FJ converts the barn into a tastefully lit cafeteria. The cows line up outside to enter the cafeteria in order of their previously-mentioned convenient index number.
Unfortunately, with so many types of food, cleaning up afterwards is very time-consuming. If Farmer John is serving K different types of food, it takes him K*K units of time to clean the barn.
To save time, FJ serves the cows in contiguous groups from the line. After each group, he cleans up the barn and sets out the food for the next group (of course, he only sets out food that cows in the any given group will eat). Determine the minimum amount of total time FJ must spend cleaning the barn. Each group consists of the next contiguous group of cows from the line; each cow belongs to exactly one group; and the barn must be cleaned up after every group, including the last one.

输入描述:

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 contains a single integer: Pi

输出描述:

* Line 1: A single integer: the minimum amount of time FJ must spend cleaning the barn.

示例1

输入
13 4 
1 
2 
1 
3 
2 
2 
3 
4 
3 
4 
3 
1 
4 
输出
11
说明
There are four types of food and thirteen cows in line. The first cow prefers type 1, the second type 2, the third type 1, etc.
The first four groups contain one cow each. The fifth group contains two cows who prefer food #2 (requiring one unit of time). The sixth group contains cows preferring foods 3, 4, 3, 4, 3 (and requires four units of time to clean). The last two groups contain one cow each. The total time is 11.

解答

滑动窗口

其他题解讲的比较完全了，我们要做的就是维护：当前位置为  时，有个左端点，使得对于第个左端点中有种食品。

则有dp方程

所以，滑动窗口内部是桶，每次加入，如果桶内新增一种食品，且超过了种，则将右移，并且删除元素，直到有一种食品在桶中清除为0，则又回复成了种。

短代码福利： 

// SeptEtavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
#define ll long long
#define il inline
#define rep(i,s,t) for(re int i=(s);i<=(t);i++)
using namespace std;

// c_ints
il int ci(){
    re char ch;int f=1;
    while(!isdigit(ch=getchar()))f= ch=='-'?-1:1 ;
    re int x= ch^'0';
    while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
    return f*x;
}

enum{N=40024,B=256};
int a[N];

// f是dp数组，l为滑动窗口左边界
// M滑动窗口内部桶，cnt为滑动窗口内食品数
int f[N],l[B];
int M[B][N],cnt[B];

int main(){
//  printf("%lld",sizeof(f)+sizeof(a)+sizeof(l)+sizeof(M)+sizeof(cnt));
//  空间 ：41306816 （41MB）

    int n= ci(); ci();
    int b= sqrt(n+0.5);
    rep(i,1,n) a[i]= ci();

//  dp初值 
    memset(f,0x3f,sizeof(int)*(n+1));
    f[0]= 0;

    rep(i,1,n){
        rep(j,1,b){

            //如果桶内新增一种食品 
            //且超过了窗口种数限制 
            //则将左端点右移 

            if( ++M[j][a[i]]==1 ){

                if( ++cnt[j]>j ){
                    while( --M[j][a[++l[j]]]!=0 );
                    cnt[j]--;
                }
            }
        }
        rep(j,1,b) f[i]= min(f[i],f[l[j]]+j*j);
    }

    printf("%d",f[n]);

    return 0;
}



来源：z7z_Eta