P3558 [POI2013]BAJ-Bytecomputer 学校平台1113数列

_Cheems · 2023-03-09 21:14:33 · 个人记录

老师说：此题爆枚比 DP 更重要。

爆枚

我们可以定义两个指针，把一个序列分成三段：-1、0、1。

例如： a1 a2 | a3 a4 | a5 a6 。

其中，a1 a2 为 -1 段，a3 a4 为 0 段，a5 a6 为 1 段。

只要计算每段的最小代价，加在一起即可。

那么怎么表达类似 -1、1 这样的序列呢？

a1 a2 | | a3 a4 a5 a6 ，其中 a1 a2 为 -1 段，a3 ~ a6 为 1 段。

同理，序列 | | a1 a2 a3 表达的是：a1 ~ a3 为1段。

爆枚做法很有参考价值，时间复杂度为 O(n^3) 。

贴上我丑陋的代码：b 数组表示修改后的 a 数组，记得判断 每段起点 这种特殊情况。

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],b[1000005],MAX=1e7,ans;
int change_1(int x)
{
    if(x<1) return 0;
    int ans=0;
    for(int i=1; i<=x;i++)
    {
        if(a[i]==-1) {b[i]=-1;continue;}
        if(i==1&&a[i]!=-1) return -1;
        if(a[i]==0) ans++,b[i]=-1;
        if(a[i]==1) ans+=2,b[i]=-1;
    }
    return ans;
}
int change_2(int x,int y)
{
    if(x>y) return 0;
    int ans=0;
    for(int i=x; i<=y;i++)
    {
        if(a[i]==0) {b[i]=0;continue;}
        if(i==x)
        {
            if(a[i]==1&&b[i-1]==-1) {ans++;b[i]=0;continue;}
            return -1;
        }
        if(a[i]==-1) return -1;
        if(a[i]==1) return -1;
    }
    return ans;
}
int change_3(int x)
{
    if(x>n) return 0;
    int ans=0;
    for(int i=x; i<=n;i++)
    {
        if(a[i]==1) {b[i]=1;continue;}
        if(i==x)
        {
            if(a[i]==1) {b[i]=1;continue;}
            return -1;
        }
        if(a[i]==-1) ans+=2;
        if(a[i]==0) ans++; 
    }
    return ans;
}
int main()
{
    cin>>n;
    ans=MAX;
    for(int i=1; i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0; i<=n+1;i++)
     for(int j=i; j<=n+1;j++)
     {
        int ans1,ans2,ans3;
        ans1=change_1(i);
        ans2=change_2(i+1,j);
        ans3=change_3(j+1);
        if(ans1==-1||ans2==-1||ans3==-1) continue;
        ans=min(ans,ans1+ans2+ans3);
     }
    ans!=MAX?cout<<ans:cout<<"BRAK";
    return 0;
 } 

DP