BZOJ 1584 DP

时间:2024-04-30 02:14:12

显然序列不能超过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++