2009. [USACO Mar09]餐厅清扫

★★☆ 输入文件：cleanup.in 输出文件：cleanup.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

很久很久以前，Framer John只会做一种食品；而现在John能给他的N（1<=N<=40000）只奶牛供应M（1<=M<=N）种不同的食品。奶牛们非常挑剔，i号奶牛只吃食品Pi（1<=Pi<=M）。

每天，奶牛们按编号排队进自助餐厅用餐。不幸的是，这么多各类的食品让清扫工作变得非常复杂。当John供应K种食品，他之后就需要K^2的时间进行清扫。

为了减少清扫的时间，John决定把排好队的奶牛划分成若干组。每一组包含一段连续的奶牛，每一次，只让一组奶牛进入餐厅。这样，他可以让清扫所需的总用时变得最小。请计算这个最小用时。

【输入格式】

第1行输入N和M，之后N行一行输入一个整数Pi。

【输出格式】

输出最小用时。

【样例输入】

13 4

【样例输出】

【提示】

前4组每组包含1只奶牛，第5组包含两只奶牛，第6组包含5只奶牛，第7、8两组各包含1只奶牛。

　　这道题发现对于一段长度为n的序列，若有K种不同的数，则它的最优解不会超过n。所以若K大于sqrt（n），则这段序列一定会被拆开，所以DP只要有超过sqrt(i)个不同的数，就可以退出。我们又发现若一个点无法更新答案，则永远也无法更新以后的答案，可以考虑用链表加速。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int maxn=;

 int a[maxn],f[maxn],nxt[maxn],pre[maxn],head[maxn],n,m,k;

 int l[maxn],r[maxn];

 int main(){

     freopen("cleanup.in","r",stdin);

     freopen("cleanup.out","w",stdout);

     scanf("%d%d",&n,&k);

     memset(f,,sizeof(f));f[]=;

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     for(int i=;i<=n;i++){

         pre[i]=head[a[i]];

         nxt[pre[i]]=i;

         head[a[i]]=i;

         l[i]=i-;

         r[i]=i+;

     }

     for(int i=;i<=n;i++){

         int ret=;

         m=ceil(sqrt(i));

         for(int j=i;j>=;j=l[j]){

             if(ret>m)break;

             if(nxt[j]>i||!nxt[j])ret++;

             else l[r[j]]=l[j],r[l[j]]=r[j];

             f[i]=min(f[i],f[l[j]]+ret*ret);

         }

     }

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

     return ;

 }

清扫