题目描述 小明对0和1两个数字情有独钟,希望世界的信息都是由这两个数字组成(很难想象小明为什么有这种想法吧)。
由于小明对0和1组成的字串有深厚的研究,他研究出一种由0和1组成字串的方法,如果任意只包含0的子串,长度不超过max0,任意只包含1的子串,长度不超过max1,且整个串最多有count0个0,count1个1。那么这个就是漂亮的数字串。
但是小明遇到问题,就是在给定了count0,count1,max0,max1的前提下,这个漂亮的数字串最长能有多长呢?这时,他找到了你(程序员),希望你帮帮他。
输入 输入包含多行,至文件结束为止。
每行四个数,依次为count0,count1,max0,max1。
输出 每组数据输出一行,一个数表示最长的超级优美无敌串的长度。
样例输入 10 10 0 0 3 5 1 1 样例输出 0 7 提示 0≤count0,count1,max0,max1≤1000000
[注意事项]
第二个样例的解释“1010101”。
最多1000组数据,其中30%的数据0≤count0,count1,max0,max1≤20,且数据组数不超过20组。
蒟蒻代码:超时 30分
#include <bits/stdc++.h>
using namespace std;
int mx, my, xx, yy, maxn = -1;
void sou(int x,int y,int nx,int ny,int ci){
if(x > xx || y > yy || nx > mx || ny > my){
return ;
}
if(ci > maxn){
maxn = ci;
}
sou(x + 1,y,nx + 1,0,ci + 1);
sou(x,y + 1,0,ny + 1,ci + 1);
}
int main(){
while(cin >> xx >> yy >> mx >> my){
maxn = -1;
if((mx == 0 && my == 0) || (xx == 0 && yy == 0)){
cout << 0 << endl;
continue;
}
sou(0,0,0,0,0);
cout << maxn << endl;
}
return 0;
}