把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1089A Alice the Fan
题目大意：爱丽丝的记录书上有50000条记录，分别记录了a,b（级别在200，分别表示排球赛中两队获得的分数总和），问当第一队大比分最优时五场比赛的具体比分，比分规则同排球规则，前四场25分，第五场15分，加时赛分差大于1获胜。

解：

很容易看出确实是dp，因为如果仅仅是在现有比分上赢一场，我只有两种情况（加时和不加时），但是要考虑的参数太多了（比赛场次，大比分，双方此时的分数，这场比赛的双方比分），而且也不知道dp要记录啥，更别说还要去记录每场的比分。
既然参数太多那就全部定位状态好了。
Dp[x][y][a][b]表示大比分为x:y，双方得分为a，b时能否成立，对，只要记录能否成立，转移时两种情况分别讨论，可以剪枝但没必要，注意x和y上的细节（得分为3的那一方一定要赢最后一场，x+y等于5时常数从25变为15），复杂度为O(44n2)，查询复杂度为O(6+5)，记录数组记录转移的位置就行。
写起来算是一个挺大的模拟，不过捋清楚之后还是挺好写的。
很多时候把dp限制在了线性和区间的一维二维上，实际上dp的维数是多少都没关系吧。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
using namespace std;
struct node {
    ll a, b, c, d;
};
ll dp[4][4][205][205];
map<ll, node> rcd[4][4][205];
void ddp() {
    dp[0][0][0][0] = 1;
    //x:y
    inc(x, 0, 4) {
        inc(y, 0, 4) {
            if (x == 3 && y == 3)break;
            inc(i, 0, 201) {
                inc(j, 0, 201) {
               //     cout << "i=" << i << " ,j=" << j << endl;
                    int cst = 25;
                    if (x +y==5)cst = 15;
                    //from x:y-1
                    if (y > 0&&x!=3) {
                            
                        inc(k, 0, i + 1) {
                            if (j < cst)break;
                            if (k >= cst-1)break;
                            if (dp[x][y - 1][i - k][j - cst] == 1) {
                                dp[x][y][i][j] = 1;
                                node xx = { x,y - 1,i - k,j - cst };
                                rcd[x][y][i][j] = xx;
                            }
                        }
                        inc(k, cst+1, 201) {
                            if (i - k + 2 < 0 || j - k < 0)break;
                            if (dp[x][y - 1][i - k + 2][j - k] == 1) {
                                dp[x][y][i][j] = 1;
                                node xx = { x,y - 1,i - k + 2,j - k };
                                rcd[x][y][i][j] = xx;
                            }
                        }
                    }
                    //from x-1:y
                    if (x > 0&&y!=3) {
                        inc(k, 0, j + 1) {
                            if (i < cst)break;
                            if (k >= cst-1)break;
                            if (dp[x - 1][y][i - cst][j - k] == 1) {
                                dp[x][y][i][j] = 1;
                                node xx = { x - 1,y,i - cst,j - k };
                                rcd[x][y][i][j] = xx;
                            }
                        }
                        inc(k, cst+1, 201) {
                            if (i - k < 0 || j - k + 2 < 0)break;
                            if (dp[x - 1][y][i - k][j - k + 2] == 1) {
                                dp[x][y][i][j] = 1;
                                node xx = { x - 1,y,i - k,j - k + 2 };
                                rcd[x][y][i][j] = xx;
                            }
                        }
                    }
                }
            }
        }
    }
  //  cout << "finished" << endl;
  //  cout << dp[1][0][25][0] << " " << dp[2][0][50][0] << " " << dp[3][0][75][0];
}
stack < pll> ans;
int main() {
	cfast;
    ddp();
    int m;
    cin >> m;
    while (m--) {
        int c1=0, c2=0;
        int a, b;
        cin >> a >> b;
        if (dp[3][0][a][b] == 1)c1 = 3, c2 = 0;
        else if (dp[3][1][a][b] == 1)c1 = 3, c2 = 1;
        else if (dp[3][2][a][b] == 1)c1 = 3, c2 = 2;
        else if (dp[2][3][a][b] == 1)c1 = 2, c2 = 3;
        else if (dp[1][3][a][b] == 1)c1 = 1, c2 = 3;
        else if (dp[0][3][a][b] == 1)c1 = 0, c2 = 3;
        else cout << "Impossible" << endl;
        if (c1 + c2 > 0) {
            cout << c1 << ":" << c2 << endl;
        }
        while (c1 + c2 > 0) {
            node xx = rcd[c1][c2][a][b];
            pll p;
            p.first = a - xx.c, p.second = b - xx.d;
            ans.push(p);
            c1 = xx.a, c2 = xx.b, a = xx.c, b = xx.d;
        }
        while (ans.size()) {
            cout << ans.top().first << ":" << ans.top().second << " ";
            if(ans.size()==1)cout << endl;
            ans.pop();
        }
    }
    
}