洛谷P2943 清理—

题目：https://www.luogu.org/problemnew/show/P2943

一眼看去就有个 n^2 的做法：f[i] = min{ f[j] + num( i - j ) * num( i - j ) } ， 1 <= j < i；

但仔细想想这个做法，发现那个num数组很不好处理；

也就是我们需要关注一个区间内食品的种类数；

不妨根据这个来调整做法，直接枚举种类数；

这样做的好处是可以进行转移，因为从 i 到 i+1 会带来一个种类数量的改变；

由此受到启发，设数组 pos[j] 为种类数是 j 时可到达的最远节点(越远越优)；

再对每个点记录一下前驱后继以便于进行种类数是否增加的判断；

cnt数组记录 pos[j] 到 i 这一段(实际的)种类数，就可以转移了。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=;

int n,m,f[maxn],pos[maxn],cnt[maxn],pre[maxn],nxt[maxn],lst[maxn],a[maxn];

int main()

{

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

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

    {

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

        pre[i]=lst[x];

        nxt[lst[x]]=i;

        lst[x]=i;

        nxt[i]=n+;

    }

    for(int i=;i*i<=n;i++)pos[i]=;//!

    memset(f,0x3f,sizeof f);

    f[]=;

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

        for(int j=;j*j<=n;j++)

        {

            if(pre[i]<pos[j])cnt[j]++;

            if(cnt[j]>j)

            {

                cnt[j]--;

                while(nxt[pos[j]]<=i)pos[j]++;

                pos[j]++;

            }

            f[i]=min(f[i],f[pos[j]-]+j*j);

        }

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

    return ;

}

巴特西

洛谷P2943 清理——DP

最新文章

热门文章