题解：P11311 漫长的小纸带

· · 题解

题外话

好久没写题解了，碰巧遇到了这题。\ 这题挺有意思的。

思路

读完题后，可发现最终答案和不同数字的个数有关，和具体数值无关，所以先把 a_i 离散化。然后考虑动态规划，设 dp_i 表示前 i 个数分段所得的最小值。先写个最简单的思路，易得转移式为 dp_i=min_{j=0}^{i-1} dp_j+w^2，其中 dp_0=0，w 表示的是 a_j 到 a_i 之间不同数字的个数。对于每个 i，从大到小枚举 j，顺便用桶记录不同数字的个数，n^2 的做法就被我们找到了，加一个小优化可得 48 分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],b[200005],dp[200005];
int lsh[200005],tot=0;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],lsh[++tot]=a[i];
    sort(lsh+1,lsh+tot+1);
    tot=unique(lsh+1,lsh+tot+1)-lsh-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
    for(int i=1;i<=n;i++){
        dp[i]=1e18;
        int w=1;
        b[a[i]]=i;
        for(int j=i-1;j>=0;j--){
            if(w*w>=dp[i])break;//小优化
            dp[i]=min(dp[i],dp[j]+w*w);
            if(b[a[j]]!=i)w++,b[a[j]]=i;
        }
    }
    cout<<dp[n];
    return 0;
}

那这个思路是不是陷入瓶颈了呢？再重新想一下哪些转移位置是真的有用的。设 dp_i 是从某个位置 j 上转移来的，而 j 若满足 a_{j-1} 是在 a_j 到 a_i 中出现过的，那么其显然不如从位置 j-1 上转移，因为多一个已出现的 a_{j-1} 无任何增加的花费，所以此时位置 j 无用，也就是说最优的 dp_i 一定不是从 j 转移过来的。把这个规律普遍化一下，就会发现对于 dp_i 来说，一个位置 j 真正有用就需要满足不存在 j+1\le k\le i，使得 a_k=a_j。我们可以用一个桶来存所有数字最后出现的位置，再用 set 来维护之间的先后顺序，每次转移都从 set 中所存的位置一一尝试选取最优解。但这样乍一看，set 的大小最多也是 i，似乎还是 n^2 的时间复杂度。但别忘了我们还有一个小优化：if(w*w>=dp[i])break;。之前这个优化的作用不明显是因为每个位置可能数字出现过也有可能没出现过，构造特定数据还是能使循环执行接近 i 次。但这回我们每访问 set 中的一个位置，w 必定加一，因为我们存的是每个数字最后一次出现的位置。所以这个代码就使我们的时间复杂度变为 O(n\sqrt n)（dp_i 的最大取值也不过是 i，而且显然会小很多），并且大概率跑不满。

正解代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],b[200005],dp[200005];
int lsh[200005],tot=0; 
set<int> s;
typedef int type;
inline type read(){
    type x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(type x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x / 10);
    putchar(x%10+'0');
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read(),lsh[++tot]=a[i];
    sort(lsh+1,lsh+tot+1);
    tot=unique(lsh+1,lsh+tot+1)-lsh-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
    for(int i=1;i<=n;i++){
        dp[i]=1e18;
        if(b[a[i]])s.erase(s.find(-b[a[i]]));
        int w=1;
        for(auto it=s.begin();it!=s.end();it++){
            int j=-*it;
            dp[i]=min(dp[i],dp[j]+w*w);
            w++;
            if(w*w>=dp[i])break;
        }
        dp[i]=min(dp[i],w*w);
        b[a[i]]=i,s.insert(-i);//存-i是在使set从大往小排列位置
    }
    write(dp[n]);
    return 0;
}

后记

点个赞吧。