自动搬运

查看原文

来自洛谷，原作者为

	ny_Dacong 你所热爱的，是你配热爱的吗？

搬运于2025-08-24 22:51:53，当前版本为作者最后更新于2025-01-11 08:57:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

发现 $0 \le a,b \le 200$，于是考虑 DP。

设 $dp_{i,j,x,y}$ 表示 A 队赢了 $i$ 分、B 队赢了 $j$ 分、A 队赢了 $x$ 场、B 队赢了 $y$ 场的情况是否合法。等于一表示合法，等于零表示不合法。

转移比较麻烦，按照题目描述一步步来。

首先考虑 $x+y = 5$ 的情况。此时是第五场，赢得本场需要 $15$ 分。枚举哪个队伍赢得本场的胜利，还要枚举输的队伍赢了多少分。所以转移：

$$dp_{i,j,x,y} = \max \begin{cases} dp_{i-15,j-k,x-1,y} (0 \le k \le \min(j,13),x \ge 1,y \not = 3) \\ dp_{i-k,j-15,x,y-1} (0 \le k \le \min(i,13),y \ge 1,x \not = 3) \\ \end{cases}$$

需要注意，转移的那个状态要满足 $x \not = 3,y \not = 3$，不然比赛就直接结束了。

然后考虑加时赛。

还是枚举哪个队伍取得胜利，同时枚举比赛结束时双方得了多少分。

$$dp_{i,j,x,y} = \max \begin{cases} dp_{i-k,j-k+2,x-1,y} (16 \le k \le \min(i,j)+2,x \ge 1,y \not = 3) \\ dp_{i-k+2,j-k,x,y-1} (16 \le k \le \min(i,j)+2,y \ge 1,x \not = 3) \\ \end{cases}$$

接着就是前 $1 \sim 4$ 场的情况。这跟上面是一样的。把 $15$ 改为 $25$ 即可。

最后记录当前状态是从哪里转移过来的，倒序输出即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
int dp[220][220][10][10];
struct node{
	int aa,bb,cc,dd;
};
node ans[220][220][10][10];
bool operator==(node x,node y){
	return x.aa == y.aa && x.bb == y.bb && x.cc == y.cc && x.dd == y.dd;
}
bool operator!=(node x,node y){
	return !(x == y);
}
void go_work(){
	dp[0][0][0][0] = 1;
	for(int i = 0; i <= 200; i++){
		for(int j = 0; j <= 200; j++){
			for(int x = 0; x <= 3; x++){
				for(int y = 0; y <= 3; y++){
					if(x+y == 5){
						if(i >= 15 && x >= 1 && y != 3){
							for(int q = 0; q <= min(13,j); q++){
								if(dp[i-15][j-q][x-1][y]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-15,j-q,x-1,y};
								}
							}
						}
						if(j >= 15 && y >= 1 && x != 3){
							for(int q = 0; q <= min(13,i); q++){
								if(dp[i-q][j-15][x][y-1]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-q,j-15,x,y-1};
								}
							}
						}
						for(int q = 16; q <= min(i,j)+2; q++){
							if(i >= q && j >= q-2 && x >= 1 && y != 3){
								if(dp[i-q][j-q+2][x-1][y]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-q,j-q+2,x-1,y};
								}
							}
							if(i >= q-2 && j >= q && y >= 1 && x != 3){
								if(dp[i-q+2][j-q][x][y-1]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-q+2,j-q,x,y-1};
								}
							}
						}
					}else{
						if(i >= 25 && x >= 1 && y != 3){
							for(int q = 0; q <= min(23,j); q++){
								if(dp[i-25][j-q][x-1][y]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-25,j-q,x-1,y};
								}
							}
						}
						if(j >= 25 && y >= 1 && x != 3){
							for(int q = 0; q <= min(23,i); q++){
								if(dp[i-q][j-25][x][y-1]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-q,j-25,x,y-1};
								}
							}
						}
						for(int q = 26; q <= min(i,j)+2; q++){
							if(i >= q && j >= q-2 && x >= 1 && y != 3){
								if(dp[i-q][j-q+2][x-1][y]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-q,j-q+2,x-1,y};
								}
							}
							if(i >= q-2 && j >= q && y >= 1 && x != 3){
								if(dp[i-q+2][j-q][x][y-1]){
									dp[i][j][x][y] = 1;
									ans[i][j][x][y] = {i-q+2,j-q,x,y-1};
								}//l
							}//u
						}//f
					}//i
				}//t
			}//u
		}//a
	}//e
}//b
stack<pair<int,int>> prt;
int main(){
	go_work();
	scanf("%d",&t);
	while(t--){
		static node tp,now;
		scanf("%d%d",&n,&m);
		while(prt.size()){
			prt.pop();
		}
		if(dp[n][m][3][0]){
			puts("3:0");
			now = (node){n,m,3,0};
			tp = ans[n][m][3][0];
			while(now != (node){0,0,0,0}){
				prt.push({now.aa-tp.aa,now.bb-tp.bb});
				now = tp;
				tp = ans[tp.aa][tp.bb][tp.cc][tp.dd];
			}
			while(prt.size()){
				printf("%d:%d ",prt.top().first,prt.top().second);
				prt.pop();
			}
			puts("");
		}else if(dp[n][m][3][1]){
			puts("3:1");
			now = (node){n,m,3,1};
			tp = ans[n][m][3][1];
			while(now != (node){0,0,0,0}){
				prt.push({now.aa-tp.aa,now.bb-tp.bb});
				now = tp;
				tp = ans[tp.aa][tp.bb][tp.cc][tp.dd];
			}
			while(prt.size()){
				printf("%d:%d ",prt.top().first,prt.top().second);
				prt.pop();
			}
			puts("");
		}else if(dp[n][m][3][2]){
			puts("3:2");
			now = (node){n,m,3,2};
			tp = ans[n][m][3][2];
			while(now != (node){0,0,0,0}){
				prt.push({now.aa-tp.aa,now.bb-tp.bb});
				now = tp;
				tp = ans[tp.aa][tp.bb][tp.cc][tp.dd];
			}
			while(prt.size()){
				printf("%d:%d ",prt.top().first,prt.top().second);
				prt.pop();
			}
			puts("");
		}else if(dp[n][m][2][3]){
			puts("2:3");
			now = (node){n,m,2,3};
			tp = ans[n][m][2][3];
			while(now != (node){0,0,0,0}){
				prt.push({now.aa-tp.aa,now.bb-tp.bb});
				now = tp;
				tp = ans[tp.aa][tp.bb][tp.cc][tp.dd];
			}
			while(prt.size()){
				printf("%d:%d ",prt.top().first,prt.top().second);
				prt.pop();
			}
			puts("");
		}else if(dp[n][m][1][3]){
			puts("1:3");
			now = (node){n,m,1,3};
			tp = ans[n][m][1][3];
			while(now != (node){0,0,0,0}){
				prt.push({now.aa-tp.aa,now.bb-tp.bb});
				now = tp;
				tp = ans[tp.aa][tp.bb][tp.cc][tp.dd];
			}
			while(prt.size()){
				printf("%d:%d ",prt.top().first,prt.top().second);
				prt.pop();
			}
			puts("");
		}else if(dp[n][m][0][3]){
			puts("0:3");
			now = (node){n,m,0,3};
			tp = ans[n][m][0][3];
			while(now != (node){0,0,0,0}){
				prt.push({now.aa-tp.aa,now.bb-tp.bb});
				now = tp;
				tp = ans[tp.aa][tp.bb][tp.cc][tp.dd];
			}
			while(prt.size()){
				printf("%d:%d ",prt.top().first,prt.top().second);
				prt.pop();
			}
			puts("");
		}else{
			puts("Impossible");
		}
	}
	return 0;
}

说这是 DP 谁信啊，分明就是 TMD 大模拟。