题解 P2943 【[USACO09MAR]清理Cleaning Up】

墨尔 · 2017-10-20 19:34:44 · 题解

首先看到题目，会想到f[i]=f[j]+t[i]k的n^2的dp方程，而n范围40000，显然超时，我们要换个思路。

仔细观察题目，发现如果把每个食物单独分段，得到时间为n，显然最少时间小于等于这个值，即每一个区间的不同食物个数最多为sqrt(n)

由此可以得到启发，设pos[j]表示区间中不同食物个数小于等于j的最远位置，即在[pos[j],i]中不同食物个数为j，由此dp方程为f[i]=min(f[pos[j]-1]+j*j)，复杂度为O(n*sqrt(n))

问题转化为如何快速求区间中不同食物个数以及pos[j]的转移。

设pre[i]表示上一个与在i位置的食物相同的食物位置，nex[i]表示下一个，last[i]表示种类为i的食物出现的最后一个位置，如果i点没有上一个则pre[i]=0，没有下一个则nex[i]=n+1，有些绕口，建议直接看下面这段代码体会：

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        pre[i]=last[p[i]];
        nex[last[p[i]]]=i;
        last[p[i]]=i;
        nex[i]=n+1;
    }

判断时，如果pre[i]<pos[j]，说明i这个点在[pos[j],i-1]中并没有出现过，设cnt[j]为pos[j]对应的出现次数，则cnt[j]++；当cnt[j]>j时，显然pos[j]应该右移，如果nex[pos[j]]<i，说明在pos[j]这个位置的食物在区间中出现了不止一次，则删除它后不同个数仍然不变，因此要不断右移，直到nex[pos[j]]>=i，此时删除它后不同个数减一

至此此题解决。

#include<cstdio>
#include<cmath>
int min(int a,int b){return a<b?a:b;}
int n,m,pos[205],f[40005],p[40005],last[40005],pre[40005],nex[40005],cnt[205];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        pre[i]=last[p[i]];
        nex[last[p[i]]]=i;
        last[p[i]]=i;
        f[i]=1e9;nex[i]=n+1;
    }
    int t=sqrt(n);for(int i=1;i<=t;i++)pos[i]=1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=t;j++)
     {
            if(pre[i]<pos[j])cnt[j]++; 
            if(cnt[j]>j)
            {
                cnt[j]--;
                while(nex[pos[j]]<i)pos[j]++;
                pos[j]++;
            }
            f[i]=min(f[pos[j]-1]+j*j,f[i]);
     }
    printf("%d\n",f[n]);
}