/ AKIOI OJ / 题库 / [whyz联测] B. 高天之歌 /

题解

1 条题解

  • 0
    @ 7 个月前

    一个重要的观察是，我们永远不会移动同一个元素两次， 因此最终的解就是移动元素的最小数量 。

    另一个关键点是，我们实际上不需要逐个执行操作。可以假设我们首先将一些元素取出，然后将它们插入到我们选择的某个位置。

    对于一些特殊情况，如果数组中至少包含一个 0 和一个 1，但没有 2，则无法找到有效解。如果数组中至少有一个 2，我们可以将所有 0 移到数组的左侧，将所有 1 移到右侧。若数组仅包含 0 或仅包含 1，那么不需要任何移动，答案为 0。

    在我们的解决方案中，我们假设至少有一个 0 和一个 1 不被移动。因此，当最优选择是移动所有的 0（或者所有的 1，这两种情况类似）时，需要处理一些特殊情况。如果我们移动所有的 0，可以将它们插入到两个 2 之间（如果存在这样的两个 2）。否则，我们需要执行一次额外的移动：取出一个 2，将其移到数组的末尾，然后将所有 0 放在后面。如果数组的第一个（或最后一个）元素已经是 2，则无需进行额外的移动。

    一般情况下，我们假设至少有一个 0 和一个 1 不被移动。我们选择删除部分 0、部分 1 以及部分 2。左边的数组（最终状态）可能会存在一些相邻的冲突元素对。删除的 2 的数量需要等于或多于这些冲突的数量。在这种情况下，我们可以找到一个有效的解决方案，因为可以将所有的 0 插入到未移动的某个 0 的旁边（对 1 也执行相同的操作）。

    我们的方法是先移除所有的 2，并在它们的位置留下空白。因此，初始成本等于数组中 2 的总数。接下来，从左到右遍历数组。当遇到 0 或 1 时，我们可以选择删除或保留它们。如果保留，我们可能需要在其前面插入一个 2 来解决潜在的冲突。当到达空白位置时，可以选择不进行操作并继续，或者插入一个 2。后者的选择会使成本减少 1，就像一开始没有移动该元素一样。

    动态规划的解决方案开始成型：

    设 d[len][numTwo][last][mask]d[\text{len}][\text{numTwo}][\text{last}][\text{mask}] 表示处理长度为 len\text{len} 的前缀时的最小成本，其中：

    • numTwo\text{numTwo} 是我们插入的 2 的数量；
    • last\text{last} 是前缀最后一个元素的值；
    • mask\text{mask} 是一个二进制掩码，两位分别表示是否至少有一个 0 和一个 1 未被移动。

    最终解可以通过检查 d[N][totalNumTwo][0/1/2][3]d[N][\text{totalNumTwo}][0/1/2][3] 来获得。递归的计算时间为 O(1)O(1)，因此时间复杂度为 O(N2)O(N^2) 。

    注意到对于某个长度 len\text{len} 的所有值，仅依赖于 len−1\text{len}-1 的值，所以滚掉一维，可以将内存优化为 O(N)O(N) 。

    #include<bits/stdc++.h>
#define IXcape cout<<endl;return 0
#define Venti cout<<"\nVenti!\n"
#define int long long
using namespace std;
const int V=5e3+10;
int cnt[4],a[V],dp[V][4][3],tmp[V][4][3];
int t,n,res,ans;

inline
int check(){
    if(cnt[2]==0&&cnt[0]!=0&&cnt[1]!=0){
        cout<<-1<<'\n';
        return 1;
    }
    if(cnt[0]==0||cnt[1]==0){
        cout<<0<<'\n';
        return 1;
    }
    return 0;
}

signed main() {
    freopen("sonnet.in","r",stdin);
    freopen("sonnet.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        memset(cnt,0,sizeof cnt);
        res=0;
        cin>>n;
        
        for(int i=0;i<n;i++){
            cin>>a[i];
            cnt[a[i]]++;
        }
        
        if(check()==1)
            continue;
            
        for(int i=0;i<n-1;i++)
            if(a[i]==2&&a[i+1]==2)
                res=1;
                
        ans=min(cnt[0],cnt[1]);
        if(res==0)
            ans+=(a[0]!=2&&a[n-1]!=2);
            
        for(int j=0;j<=cnt[2];j++)
            for(int res=0;res<=3;res++)
                for(int la=0;la<=2;la++)
                    dp[j][res][la]=(res==3)?0:n;
                    
        for(int i=n-1;i>=0;--i){
            for(int j=0;j<=cnt[2];j++)
                for(int res=0;res<=3;res++)
                    for(int la=0;la<=2;la++){
                        int ans=n;
                        if(a[i]==2){
                            if(j!=0)
                                ans=min(ans,dp[j-1][res][2]-1);
                            ans=min(ans,dp[j][res][la]);
                        } 
                        else{
                            if(la==a[i]||la==2) 
                                ans=min(ans,dp[j][res|(1<<a[i])][a[i]]);
                            else if(j!=0) 
                                ans=min(ans,dp[j-1][res|(1<<a[i])][a[i]]);
                            ans=min(ans,dp[j][res][la]+1);
                        }
                        tmp[j][res][la]=ans;
                    }
            for(int j=0;j<=cnt[2];j++)
                for(int res=0;res<=3;res++)
                    for(int la=0;la<=2;la++) 
                        dp[j][res][la]=tmp[j][res][la];
        }
        
        ans=min(ans,cnt[2]+dp[cnt[2]][0][2]);
        cout<<(ans>=n?-1:ans)<<'\n';
    }
    IXcape;
}
    Copy
  • 1

[whyz联测] B. 高天之歌

信息

ID
1091
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. Language
  1. © 2024 oj.xzynb.top
  2. Powered by AKIOIOJ and Vijos