BZOJ 1584 [Usaco2009 Mar]Cleaning Up 打扫卫生

作者: MayFlyyh 分类: DP 发布时间: 2018-08-16 16:07 ė 6 没有评论

有N头奶牛,每头那牛都有一个标号Pi,1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段,定义每段的不河蟹度为:若这段里有k个不同的数,那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和。

求最小不和谐度哇


考虑如果把每一只牛都作为1段,那么不和谐度为n,所以每一段的种类不可能超过\sqrt{n},才能保证可能最优

本题有两种解法,都是n*\sqrt{n} 的,第二种的跑起来要松一些。

解法1:

pre[i]表示在此位置之前并且离此位置最近的一个数a[i]的坐标,nxt[i]表示此位置之后并且离此位置最近的一个数a[i]的坐标(相同的数的前驱后继)

pos[j]表示pos[j]+1到当前位置有j个不同的元素(也就是说pos[j]中存储的是下标)

cnt[j]表示pos[j]到当前位置的元素个数(一般情况为j)

考虑i-1到i转移,那么就会多一个数a[i]

对每个j来说,如果pre[i]大于等于pos[j],那么cnt[j]不变
否则cnt[j]++,然后对于a[pos[j]]来说,如果pos[j]上的数的后继小于i,那么pos[j]就要向后移动1格

其中j只用枚举到\sqrt{n}

CODE:

#include<bits/stdc++.h>
std::map<int,int> p;
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=(1ll*x<<3)+(1ll*x<<1)+c-'0';c=getchar();}
    return flag*x;
}
int a[(int)1e5],pre[(int)1e5],nxt[(int)1e5];
int pos[(int)1e5],cnt[(int)1e5],f[(int)1e5];
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i=1;i<=n;++i) a[i]=read(),f[i]=1e9+7;
        for(int i=1;i<=n;++i){
            if(p.count(a[i])) pre[i]=p[a[i]];
            p[a[i]]=i;
        }
        p.clear();
        for(int i=n;i;--i){
            if(p.count(a[i])) nxt[i]=p[a[i]];
            else nxt[i]=n+1;
            p[a[i]]=i;
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j*j<=n;++j)
                if(pre[i]<=pos[j]) cnt[j]++;
            for(int j=1;j*j<=n;++j){
                if(cnt[j]>j){
                    ++pos[j];
                    while(nxt[pos[j]]<=i) 
                        ++pos[j];
                    --cnt[j];
                }
            }
            for(int j=1;j*j<=n;++j) f[i]=std::min(f[i],f[pos[j]]+j*j);
        }
        printf("%d\n",f[n]);
    }
    return 0;
}

解法2:

双向链表连接每个数,当考虑完一个数以后,就把与这个数字相同的数,并且在这个数字出现之前的数字从双向链表中删去。

这样从当前这个数字往后枚举,最多枚举\sqrt{位置标号}个即可

因为再算当前数字之前,是向前枚举是必定包含更前的数的,所以每次保留最后一个数即可,复杂度Σ\sqrt{i}+n*log(n) (1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 50010;
const int inf = 0x3f3f3f3f;

int a[maxn], pre[maxn], nxt[maxn], dp[maxn];
map<int, int> mp;
int m ;
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        scanf("%d",&m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            pre[i] = i - 1;
            nxt[i] = i + 1;
        }

        mp.clear();
        memset(dp, inf, sizeof(dp));
        dp[0] = 0, pre[0] = -1;
        for (int i = 1; i <= n; i++) {
            if (!mp.count(a[i])) mp[a[i]] = i;
            else {
                int id = mp[a[i]];
                nxt[pre[id]] = nxt[id];
                pre[nxt[id]] = pre[id];
                mp[a[i]] = i;
            }

            int cnt = 0;
            for (int j = pre[i]; j != -1; j = pre[j]) {
                cnt++;
                dp[i] = min(dp[i], dp[j] + cnt * cnt);
                if (cnt * cnt > i)
                    break;
            }
        }

        printf("%d\n", dp[n]);
    }
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/325

0

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部