美团9.27 三四五题

//第三题dp
int main() {
	int n;
	cin >> n;
	string s;
	getline(cin, s);
	getline(cin, s);
	int e = -1;
	int l = s.size();
	vector<int> v(l, 0);
	int re = 0;
	if (s[0] == 'E'){v[0] = 1; e = 0;
}
    else v[0] = -1;
	for (int i = 1; i < l; i++) {
		if (s[i] == 'E') {
			if (e != -1) {
				v[i] = max(1, v[e] + 1 - (i - e-1));
				e = i;

			}
			else {
				v[i] = 1; e = i;
			}
			re = max(re, v[i]);
		}
		else {
			if (e != -1) {
				v[i] = max(-1, v[e]-1 - (i - e - 1));

			}
			else {
				v[i] = -1;
			}
			re = max(re, v[i]);
		}
	}
	cout << re;
}

//第四题bfs
int main() {
	int n, m, x1, y1, x2, y2;
	cin >> n >> m >> x1>>y1>>x2>>y2;
	x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1;
	vector<vector<int>> v(n, vector<int>(m, 0));
	vector<vector<int>> vv(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int ii = 0; ii < m; ii++) {
			cin >> v[i][ii];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int ii = 0; ii < m; ii++) {
			cin >> vv[i][ii];
		}
	}
	vector<vector<int>> sig(n, vector<int>(m, 0));
	int re = 0;
	sig[x1][y1] = 1;
	queue < vector<int>> q;
	q.push({ x1,y1,0 });
	sig[x1][y1] = 1;
	while (!q.empty()) {
		auto k = q.front();
		q.pop();
		int x = k[0], y = k[1], res = k[2];
		if (x == x2 && y == y2) {
			cout << res;
			break;
		}
		if (x < 0 || y < 0 || x >= n || y >= m) continue;
		int a = v[x][y], b = vv[x][y];
		int sum = a + b;
		if (res%sum < a) {
			if (x + 1 < n && !sig[x + 1][y])
			{
				q.push({ x + 1,y,res + 1 }); sig[x + 1][y] = 1;
			}
			if (x - 1 >= 0 && !sig[x - 1][y])
			{
				q.push({ x - 1,y,res + 1 }); sig[x - 1][y] = 1;
			}

		}
		else {
			if (y + 1 < m && !sig[x][y + 1])
			{
				q.push({ x,y + 1,res + 1 }); sig[x][y + 1] = 1;
			}
				if (y - 1 >= 0 && !sig[x][y - 1])
				{
					q.push({ x,y - 1,res + 1 }); sig[x][y - 1] = 1;
				}

		}
		q.push({ x,y,res + 1 });
	}

}

//第五题最小生成树思想下的数位dp
int main() {
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int n;
		cin >> n;
		vector<vector<int>> vv(n, vector<int>(n, 0));
		for (int i = 0; i < n; i++) {
			for (int ii = 0; ii < n; ii++) {
				cin >> vv[i][ii];
			}
		}
		int l = 1 << n;
		int re = INT_MAX / 2;
		vector<vector<int>> v(n, vector<int>(l, INT_MAX / 2));
		for (int i = 0; i < n; i++) v[i][0] = 0;
		for (int i = 1; i < l; i++) {
			for (int j = 0; j < n; j++) {
				if (((i >> j) & 1) == 0) {
					for (int k = 0; k < n; k++) {
						if (((i >> k) & 1) == 1)
							v[j][i] = min(v[j][i], vv[j][k] + v[k][i ^ (1 << k)]);
					}
					if ((i | (1 << j)) == l - 1) re = min(v[j][i], (int)re);
				}
			}
		}
		cout << re<<endl;
	}
}