BZOJ 1584 DP

显然序列不能超过sqrt(n)，因为最差情况是每个都独立答案为n

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 const int Maxn=;

 int Next[Maxn],F[Maxn],a[Maxn],B[Maxn],Last[Maxn],n,m,Top;

 inline int Min(int x,int y) {return x>y?y:x;}

 int main()

 {

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

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     int Block=floor(sqrt(n));

     for (int i=;i<=Block;i++) B[i]=;

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

     {

         Next[i]=Last[a[i]];

         Last[a[i]]=i;

         for (int j=;j<=Min(Top,Block);j++)

             if (B[j]>Next[i])

             {

                 while (true)

                 {

                     B[j]++;

                     if (B[j]-==Last[a[B[j]-]]) break;

                 }

             }

         if (!Next[i]) Top++;

         F[i]=i;

         for (int j=;j<=Min(Top,Block);j++) F[i]=Min(F[i],F[B[j]-]+j*j);

     }

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

     return ;

 }

C++

相关文章