站外题求助
  • 板块学术版
  • 楼主inkchara
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/2/10 21:53
  • 上次更新2023/10/28 08:58:14
查看原帖
站外题求助
578008
inkchara楼主2022/2/10 21:53

题目描述 小明对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;
}
2022/2/10 21:53
加载中...