[CF1089A]Alice the Fan(动态规划预处理)

题面

传送门

题目描述

爱丽丝是排球的忠实粉丝，特别是非常强大的“A队”。
排球比赛最多由五局组成。 在每局比赛中，球队每赢一球得1分。 在前四局比赛中，一旦一支球队得分至少为25分，本局比赛结束。而第五局比赛，一旦一支球队得分至少达到15分，则本局比赛结束。 此外，如果其中一支球队得分为25（或第五局为15分），而另一支球队得分为24（或第五局为14），则该局将继续下去，直到球队得分之间的绝对差异变为2。 当其中一支球队赢得三局时，比赛结束。比赛得分是每支球队赢得的局数。
爱丽丝找到了一本书，其中包含“A队”所有比赛的所有结果。这本书很旧，书的某些部分变得难以理解。 爱丽丝无法阅读有关每支球队赢了多少局的信息，她无法阅读每局中每支球队得分多少的信息，她甚至不知道某一场比赛中的打了多少局。 她拥有的唯一信息是在一场比赛中每支球队在所有局比赛中得分的总数。
Alice想知道“A队”在每场比赛中可以取得的最佳比赛得分是多少。 “A队”赢得的局数与对手之间的差异越大，比赛得分越高。 找到最佳比赛分数或者得出结论：没有比赛可能会得到这样结果。
如果有多种可能方案，输出任何一种方案即可。

输入格式：

$m$组数据，每组两个数$a,b$。
分别代表’A队’和对手得分数总和。
$1\le m\le 50000,0\le a,b\le 200$

输出格式:

如果无解输出Impossible,否则第一行输出比赛得分，第二行依次输出每场得分。
具体格式请见样例。

题解

今天测试里的最简单的题。
差点没签成到…我太菜了…
最开始感觉这是一道恶心的模拟题。
仔细观察了一下数据范围，发现$a,b\le 200$，感觉又像一个$O(n^3)$的预处理暴力dp。
然后试了一下，结果可做…

设$dp[A][B][x][y]$为A队得分总和为$A$,B队得分总和为$B$,现在的比分是$x:y$时是否有解。
再开一个vector $ans[A][B][x][y]$保存答案。

然后转移就很好写了:
[设$winscore$为正常情况下能够获胜的分数]
1.该局有一个队伍得分在$winscore+1$分及以上，此时两组分数相差2:
$$dp[A+val][B+val?2][x+1][y]=dp[A][B][x][y]$$
$$dp[A+val?2][B+val][x][y+1]=dp[A][B][x][y]$$
2.该局有一个队伍得分在$winscore?1$分以下，此时有一组分数为为$winscore$，另外一组的得分任意：
$$dp[A+winscore][B+val][x+1][y]=dp[A][B][x][y]$$
$$dp[A+val][B+winscore][x][y+1]=dp[A][B][x][y]$$
其实这题细节也不多，只是很多人(包括我)嗅到这样熟悉的毒瘤模拟题气息就开始无脑模拟了。
时间复杂度:$O(9n^3)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
#define MAXN 200
#define LL long long
#define INF 10000
#define MOD 1000000000
#define PB push_back
#define MP make_pair
#define FR first
#define SE second
int dp[MAXN+5][MAXN+5][4][4];
vector< pair<int,int> > ans[MAXN+5][MAXN+5][4][4];
int T;
int vx[]={
    3,3,3,2,1,0},vy[]={
    0,1,2,3,3,3};
int main()
{
    freopen("match.in","r",stdin);freopen("match.out","w",stdout);dp[0][0][0][0]=1;for(int A=0;A<=200;A++)for(int B=0;B<=200;B++)for(int x=0;x<=2;x++)for(int y=0;y<=2;y++){
    int maxs=25;if(x+y==4)maxs=15;if(!dp[A][B][x][y])continue;for(int val=maxs+1;val<=200;val++){
    if(A+val<=200&&B+val-2<=200&&!dp[A+val][B+val-2][x+1][y]){
    dp[A+val][B+val-2][x+1][y]=1;ans[A+val][B+val-2][x+1][y]=ans[A][B][x][y];ans[A+val][B+val-2][x+1][y].PB(MP(val,val-2));}if(A+val-2<=200&&B+val<=200&&!dp[A+val-2][B+val][x][y+1]){
    dp[A+val-2][B+val][x][y+1]=1;ans[A+val-2][B+val][x][y+1]=ans[A][B][x][y];ans[A+val-2][B+val][x][y+1].PB(MP(val-2,val));}}for(int val=0;val<maxs-1;val++){
    if(A+maxs<=200&&B+val<=200&&!dp[A+maxs][B+val][x+1][y]){
    dp[A+maxs][B+val][x+1][y]=1;ans[A+maxs][B+val][x+1][y]=ans[A][B][x][y];ans[A+maxs][B+val][x+1][y].PB(MP(maxs,val));}if(A+val<=200&&B+maxs<=200&&!dp[A+val][B+maxs][x][y+1]){
    dp[A+val][B+maxs][x][y+1]=1;ans[A+val][B+maxs][x][y+1]=ans[A][B][x][y];ans[A+val][B+maxs][x][y+1].PB(MP(val,maxs));}}}scanf("%d",&T);while(T--){
    int A,B,x=-1,y;scanf("%d%d",&A,&B);for(int v=0;v<6;v++)if(dp[A][B][vx[v]][vy[v]]){
    x=vx[v],y=vy[v];break;}if(x==-1){
    printf("Impossible\n");continue;}printf("%d:%d\n",x,y);for(int i=0;i<ans[A][B][x][y].size();i++)printf("%d:%d ",ans[A][B][x][y][i].FR,ans[A][B][x][y][i].SE);printf("\n");}
}