记录编号 |
453506 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[USACO Mar09]餐厅清扫 |
最终得分 |
100 |
用户昵称 |
~玖湫~ |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.023 s |
提交时间 |
2017-09-21 16:56:06 |
内存使用 |
0.55 MiB |
显示代码纯文本
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=40000+10;
int n,m,tot,js,l,r;
int val[M],f[M],pre[M],nxt[M],col[M],pos[M],num[M];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int DK(){
freopen("cleanup.in","r",stdin);
freopen("cleanup.out","w",stdout);
memset(nxt,0x3f,sizeof(nxt));
n=read();m=read();int xx;
for(int i=1;i<=n;++i){
xx=read();
if(xx==val[tot]) continue;
val[++tot]=xx;
}
for(int i=1;i<=tot;++i){
int id=col[val[i]];
pre[i]=id;nxt[id]=i;
col[val[i]]=i;
}nxt[0]=0;num[1]=1;
for(int i=2;i<=tot;++i) {num[i]=num[i-1];if(!pre[i]) num[i]+=1;}
for(int i=1;i<=tot;++i) f[i]=i;
pos[1]=1;
for(int i=2;i<=tot;++i){
int lim=sqrt(f[i-1]+1);
int id=pre[i];
for(int j=1;j<=lim;++j){
if(num[i]==j) {pos[j]=1;break;}
if(id<pos[j]){
for(int k=pos[j];k<=i;++k)
if(nxt[k]>i) {pos[j]=k+1;break;}
}else{
if(pos[j]) continue;
int k=pos[j-1]-1;
for(;k>=1;--k) if(nxt[k]>i) {pos[j]=k;break;}
--k;
while(nxt[k]<=i) --k;
pos[j]=k+1;
}
}
for(int j=1;j<=lim;++j){
if(!pos[j]) break;
f[i]=min(f[i],f[pos[j]-1]+j*j);
}
}printf("%d\n",f[tot]);
return 0;
}
int dk=DK();
int main(){;}