P9791 [NERC2018] Alice the Fan 题解

· · 题解

思路

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

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

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

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

\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，不然比赛就直接结束了。

然后考虑加时赛。

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

\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 大模拟。