题解 P8001

· · 题解

题意：

题目里说的挺简洁明白的，换句话说也可以是最小化相邻字符不同的个数。

很明显，这个也可以理解成：每次取所有串前面一样的数，使取的次数最少。

思路：

首先，取的方法决定，该取一个数就一定要把这一个串前面的这个数全部取出来，所以一个串取的次数最少就是相邻字符不同的个数再 +1。

每次要把所有的串前面的数都取出来，所以每个串取的次数都应该考虑。整体能够取的次数就是所有串能取次数的最大值。

然后就出来一份代码：

#include<iostream>
#include<cstring>
#define ri register int
using namespace std;
int n,l,tot,cnt,maxcnt;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(ri i=1;i<=n;i++){
        cin>>s;
        l=s.length(),cnt=0;
        tot+=l;//一共相邻的字符数，就是全部字符的个数-1
        for(ri j=1;j<l;j++)
            if(s[j]!=s[j-1])//求相邻字符不同的个数
                cnt++;
        maxcnt=cnt>maxcnt?cnt:maxcnt;//取最大值
    }
    tot--;
    cout<<tot-maxcnt<<endl;//最后减去不同的个数
    return 0;
}

然而只有 50pts。

原因应该很明显，一个串的开头可能是 0 或者 1，但是要是取的话，第一次可能取的字符不能是这个串的开头。换句话说，第一次取的如果是 0，但是这个串的开头是 1，那么这个串暂时取不了，所以此时其实应该再多算一次。

所以我们对于每个串，都同时考虑最先取 0 或 1 的情况，然后取这两种情况的最优方案即可。

程序如下：

#include<iostream>
#include<cstring>
#define ri register int
using namespace std;
int n,l,tot,cnt0,cnt1,maxcnt0,maxcnt1,maxcnt;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(ri i=1;i<=n;i++){
        cin>>s;
        l=s.length(),cnt0=cnt1=0;
        tot+=l;
        if(s[0]=='0')cnt1++;//如果字符串开头是0，那么一开始取1的次数+1
        if(s[0]=='1')cnt0++;//反之亦然
        for(ri j=1;j<l;j++)
            if(s[j]!=s[j-1])
                cnt0++,cnt1++;
        maxcnt0=cnt0>maxcnt0?cnt0:maxcnt0;
        maxcnt1=cnt1>maxcnt1?cnt1:maxcnt1;
    }
    maxcnt=min(maxcnt0,maxcnt1);//取其最小值
    tot--;
    cout<<tot-maxcnt<<endl;
    return 0;
}

THE END