题解

贴个毫无思维难度的神秘赛时做法。

注意到 $x,y,z\le 100$，所以所有 $x,y,z$ 的情况不超过 $2\times 10^6$。显然可以记忆化搜索。多测不要清空。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int dpsiz[105][105][105];
int dpwa[105][105][105];
bool vis[105][105][105];
void dfs(int x, int y, int z){
	if(x == 0 && y == 0 && z == 0) return;
	if(vis[x][y][z]) return;
	vis[x][y][z] = 1;
	if(x > 0 && y > 0){
		dfs(x - 1, y - 1, z);
		if(dpsiz[x][y][z] < dpsiz[x - 1][y - 1][z] + 1 || dpsiz[x][y][z] == dpsiz[x - 1][y - 1][z] + 1 && dpwa[x][y][z] > dpwa[x - 1][y - 1][z]){
			dpsiz[x][y][z] = dpsiz[x - 1][y - 1][z] + 1;
			dpwa[x][y][z] = dpwa[x - 1][y - 1][z];
		}
	}
	if(x > 1){
		dfs(x - 2, y, z);
		if(dpsiz[x][y][z] < dpsiz[x - 2][y][z] + 1 || dpsiz[x][y][z] == dpsiz[x - 2][y][z] + 1 && dpwa[x][y][z] > dpwa[x - 2][y][z]){
			dpsiz[x][y][z] = dpsiz[x - 2][y][z] + 1;
			dpwa[x][y][z] = dpwa[x - 2][y][z];
		}
	}
	if(x > 0 && z > 0){
		dfs(x - 1, y, z - 1);
		if(dpsiz[x][y][z] < dpsiz[x - 1][y][z - 1] + 1 || dpsiz[x][y][z] == dpsiz[x - 1][y][z - 1] + 1 && dpwa[x][y][z] > dpwa[x - 1][y][z - 1] + 1){
			dpsiz[x][y][z] = dpsiz[x - 1][y][z - 1] + 1;
			dpwa[x][y][z] = dpwa[x - 1][y][z - 1] + 1;
		}
	}
}
void solve(){
	int x, y, z;
	cin >> x >> y >> z;
	dfs(x, y, z);
	cout << dpsiz[x][y][z] << ' ' << dpwa[x][y][z] << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度 $O(V^3)$，其中 $V=100$。