题解 P1620 【漂亮字串】

ex_jason · 2017-11-08 20:12:03 · 题解

从整体上对题目进行分析，此题共有三种情况：

（1）0

有一方为0，则结果为另一方的max；

两方都为0,则结果为0；

（2）一方多，另一方不够用，满足（contx+1）*maxo<=counto或则（conto+1）*maxx<=countx

结果为：（contx+1）*maxo+counto （X不够用）

或则

（cont0+1）*maxx+counto (O不够用)

也即，不够用的一方即使每次只取一个作为分隔符都不够用的。

比如，20 5 2 2

则最长的超级优美无敌串为：OOXOOXOOXOOXOOXOO

(3)其它情况，则结果为 maxn+maxm

除去（1）（2）两种特殊情况，则其他情况中所有的字母都可以用上。

比如8 6 3 2

则最长的超级优美无敌串为：OOOXXOOOXXOOXX

#include<iostream>
using namespace std;
int main()
{
    long long counto,countx,maxo,maxx;
    while (cin>>counto>>countx>>maxo>>maxx)
    {
        maxo=min(counto,maxo);
        maxx=min(countx,maxx);
        if (maxo==0) cout<<maxx<<endl;
        else if (maxx==0) cout<<maxo<<endl;
        else if ((counto+1)*maxx<countx) cout<<(counto+1)*maxx+counto<<endl;
        else if ((countx+1)*maxo<counto) cout<<(countx+1)*maxo+countx<<endl;
        else cout<<counto+countx<<endl;
    }
    return 0;
}