求助,为什么50分!!!
查看原帖
求助,为什么50分!!!
183881
_shy楼主2020/5/6 14:11
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <ctime>
#include <sstream>
#include <vector>
using namespace std;
const int maxn = 500010; int dpa[maxn][3], dpb[maxn][3], son[maxn][3], tot; 
char s[maxn];
void MakeTree (int root)
{
	tot++; if (s[root] == '0') return;
	if (s[root] == '1') {son[root][1] = root + 1; son[root][0] = 1; MakeTree (root + 1);}
	if (s[root] == '2') {son[root][0] = 2; son[root][1] = root + 1; MakeTree (root + 1); son[root][2] = tot + 1; MakeTree (tot + 1);}
}
void TreeDP (int x)
{
	if (dpa[x][0] != -1) return;
	if (son[x][0] == 0) {dpa[x][0] = dpa[x][2] = dpb[x][0] = dpb[x][2] = 0; dpa[x][1] = dpb[x][1] = 1; return;}
	if (son[x][0] == 1) 
	{
		TreeDP (son[x][1]); 
		dpa[x][0] = max (dpa[son[x][1]][1], dpa[son[x][1]][2]); dpa[x][1] = max (dpa[son[x][1]][0], dpa[son[x][1]][2]) + 1; dpa[x][2] = max (dpa[son[x][1]][0], dpa[son[x][1]][1]);
		dpb[x][0] = min (dpb[son[x][1]][1], dpb[son[x][1]][2]); dpb[x][1] = min (dpb[son[x][1]][0], dpb[son[x][1]][2]) + 1; dpb[x][2] = min (dpb[son[x][1]][0], dpb[son[x][1]][1]);
	}
	if (son[x][0] == 2)
	{
		TreeDP (son[x][1]); TreeDP (son[x][2]);
		dpa[x][0] = max (dpa[son[x][1]][1] + dpa[son[x][2]][2], dpa[son[x][1]][2] + dpa[son[x][2]][1]);
		dpa[x][1] = 1 + max (dpa[son[x][1]][0] + dpa[son[x][2]][2], dpa[son[x][1]][2] + dpa[son[x][2]][0]);
		dpa[x][2] = max (dpa[son[x][1]][1] + dpa[son[x][2]][0], dpa[son[x][1]][0] + dpa[son[x][2]][1]);
		dpb[x][0] = min (dpb[son[x][1]][1] + dpb[son[x][2]][2], dpb[son[x][1]][2] + dpb[son[x][2]][1]);
		dpb[x][1] = 1 + min (dpb[son[x][1]][0] + dpb[son[x][2]][2], dpb[son[x][1]][2] + dpb[son[x][2]][0]);
		dpb[x][2] = min (dpb[son[x][1]][1] + dpb[son[x][2]][0], dpb[son[x][1]][0] + dpb[son[x][2]][1]);
	}
}
int main ()
{
	scanf ("%s", &s);
	MakeTree (0); memset (dpa, -1, sizeof (dpa)); memset (dpb, -1, sizeof (dpb)); TreeDP (0);
	printf ("%d %d", max (dpa[0][0], max (dpa[0][1], dpa[0][2])), min (dpb[0][0], min (dpb[0][1], dpb[0][2])));
	return 0;
}
2020/5/6 14:11
加载中...