问题 A: Cleaning Up 打扫卫生
时间限制: 1 Sec 内存限制: 128 MB
题目描述
[Usaco2009 Mar]Cleaning Up 打扫卫生
Description
有N头奶牛，每头那牛都有一个标号Pi，1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有k个不同的数，那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和。
Input
第一行：两个整数N，M
第2..N+1行：N个整数代表每个奶牛的编号
Output
一个整数，代表最小不河蟹度
Sample Input
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
Sample Output
11
我承认我没打正解。。正解N^1.5，我打了个假N^2.
对于f[i],应该是把j~i一段合并起来，f[i]=min(f[j-1]+s*s);
s为区间j~i中出现的个数。
剪枝：倒着找，s*s>i则直接跳出。
就这样水过了。。。
#pragma GCC optimize("O3")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 40005
#define ll long long
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){
if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f;
}
int n,m,tot,a[N],f[N];bool vis[N];
int main()
{n=read();m=read();int x;memset(f,120,sizeof(f));for(int i=1;i<=n;i++){x=read();if(x==a[tot])continue;a[++tot]=x;}f[0]=0;for(int i=1;i<=tot;i++){memset(vis,0,sizeof(vis));int s=0;f[i]=i;for(int j=i;j>0;j--){if(s*s>i)break;if(!vis[a[j]])vis[a[j]]=1,s++;if(f[i]>f[j-1]+s*s)f[i]=f[j-1]+s*s;}//cout<<f[i]<<endl;}cout<<f[tot];
}