• 大三第四周学习笔记

    周一

    最近补一补icpc网络赛的题目

    C Delete the Tree

    签到题，但是当时卡了一下

    首先每次操作都是删一个点，那么要删完肯定是n次操作。

    所以就是让删除操作尽可能少。

    可以发现，度数为1的点不能执行2操作，必须执行1操作，所以度数为1的点的个数是答案的下界。

    那么有达到这个下界的做法呢？度数为1的点只有两种情况，一种是叶子，一种是根节点然后它只有一个儿子。

    我们可以从叶子开始，删叶子使得叶子的父亲度数为2，然后执行2操作把父亲删掉，然后叶子就有新的父亲，然后继续删叶子使得父亲度数为2，一直重复，这样可以删完所有的点。

    一开始WA了一发，后面注意到数据范围还有n=1的情况，这时度数为0。

    以后写题时要注意数据范围里面n特别小的情况，很可能要特判

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 1e6 + 10;
    7. int d[N], n;
    8.  
    9. int main()
    10. { 
    11.     int T; scanf("%d", &T);
    12.     while(T--)
    13.     {
    14.         scanf("%d", &n);
    15.         _for(i, 1, n) d[i] = 0;
    16.         _for(i, 1, n - 1)
    17.         {
    18.             int u, v;
    19.             scanf("%d%d", &u, &v);
    20.             d[u]++; d[v]++;
    21.         }
    22.  
    23.         int ans = 0;
    24.         _for(i, 1, n)
    25.             if(d[i] <= 1)
    26.                 ans++;
    27.         printf("%d\n", ans);
    28.     }
    29.  
    30.     return 0;
    31. }

    D Find the Number（打表）

    当时就想着打表，可以算出最大是C(20, 10)，当时把阶乘写出来感觉很大没去算，其实算一下挺小的。所以可以直接爆搜打表。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. set<int> s;
    7.  
    8. void dfs(int x, int num, int pos)
    9. {
    10.     if(num == 0)
    11.     {
    12.         if(x <= 1e9) s.insert(x);
    13.         return;
    14.     }
    15.     if(pos == 30) return;
    16.  
    17.     dfs(x | 1 << pos, num - 1, pos + 1);
    18.     dfs(x, num, pos + 1);
    19. }
    20.  
    21. int main()
    22. { 
    23.     _for(i, 1, 16)
    24.         dfs(1 << i, i - 1, i + 1);
    25.     
    26.     int T; scanf("%d", &T);
    27.     while(T--)
    28.     {
    29.         int l, r;
    30.         scanf("%d%d", &l, &r);
    31.  
    32.         auto it = s.lower_bound(l);
    33.         if(it != s.end() && *it <= r) printf("%d\n", *it);
    34.         else puts("-1");
    35.     }
    36.  
    37.     return 0;
    38. }

    G Read the Documentation（dp）

    还是需要多练习dp，dp在比赛中非常常见

    充分利用n小，最长只有4段的条件

    用dp[i][p1][p2][p3][p4]状态的最优解，其实想到这个状态下面就很简单了

    限制一下p1 p2 p3 p4的上界，然后由于最多往前i-5,i到i-5有6个，所以滚动数组将下标模6

    然后因为中间要空一格，所以前一个状态可能到-1，而-1却是合法的，这时要处理一下。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 110;
    8. ll dp[6][55][35][27][22], k[5], x[5], s[N];
    9. int n, T;
    10.  
    11. int main()
    12. { 
    13.     scanf("%d%d", &n, &T);
    14.     _for(i, 1, 4)
    15.     {
    16.         scanf("%lld", &x[i]);
    17.         k[i] = k[i - 1] + x[i];
    18.     }
    19.     _for(i, 1, n)
    20.     {
    21.         ll x; scanf("%lld", &x);
    22.         s[i] = s[i - 1] + x;
    23.     }
    24.  
    25.     ll ans = 0;
    26.     _for(i, 1, n)
    27.         _for(p1, 0, n / 2 + 1)
    28.              _for(p2, 0, n / 3 + 1)
    29.                 _for(p3, 0, n / 4 + 1)
    30.                     _for(p4, 0, n / 5 + 1)
    31.                     {
    32.                         if(p1 * k[1] + p2 * k[2] + p3 * k[3] + p4 * k[4] > T) break;
    33.  
    34.                         ll res = dp[(i - 1 + 6) % 6][p1][p2][p3][p4];
    35.                         if(p1 - 1 >= 0 && i - 2 >= -1) res = max(res, dp[(i - 2 + 6) % 6][p1 - 1][p2][p3][p4] + s[i] - s[i - 1]);
    36.                         if(p2 - 1 >= 0 && i - 3 >= -1) res = max(res, dp[(i - 3 + 6) % 6][p1][p2 - 1][p3][p4] + s[i] - s[i - 2]);
    37.                         if(p3 - 1 >= 0 && i - 4 >= -1) res = max(res, dp[(i - 4 + 6) % 6][p1][p2][p3 - 1][p4] + s[i] - s[i - 3]);
    38.                         if(p4 - 1 >= 0 && i - 5 >= -1) res = max(res, dp[(i - 5 + 6) % 6][p1][p2][p3][p4 - 1] + s[i] - s[i - 4]);
    39.  
    40.                         dp[i % 6][p1][p2][p3][p4] = res;
    41.                         if(i == n) ans = max(ans, dp[i % 6][p1][p2][p3][p4]);
    42.                     }
    43.     printf("%lld\n", ans);
    44.  
    45.     return 0;
    46. }

    L LCS-like Problem（dp）

    这题当时我想到从t中处理一个ban[][]数组，然后再s中dp找一个最长的不会被ban的序列

    我卡住点的在于，如果当前要选一个字符，那么显然要和之前选过的所有字符看会不会被ban，那么是很费时间的。

    其实，只需要判断最近的那个是否被ban，如果最近的那个不会被ban，那么和前面所有的都不会被ban

    因为考虑s和t匹配，如果s中ij  那么就有在t中的子序列恰好是s中反过来的。

    那么新来一个字符，如果它不和最近的冲突，那么它在t中匹配一定在这个最近的之前，也就在所有的之前。

    知道这一点后就很好处理了。

    首先可能出现s中的字符t中没有匹配的情况，这种时候这些字符是一定选的，处理一下就好。

    那么用dp[j]表示以字符j结尾的最长序列，那么每次对当前的s[i]，枚举j，看能不能加上即可

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. int dp[30], ban[30][30], vis[30], ans;
    7.  
    8. int main()
    9. { 
    10.     string s, t;
    11.     cin >> s >> t;
    13.     int len = t.size();
    14.     for(int i = len - 1; i >= 0; i--)
    15.     {
    16.         _for(j, 0, 25)
    17.             if(vis[j])
    18.                 ban[t[i] - 'a'][j] = 1;
    19.         vis[t[i] - 'a'] = 1;
    20.     }
    21.  
    22.     for(auto x: s)
    23.     {
    24.         if(!vis[x - 'a']) ans++;
    25.         else 
    26.         {
    27.             int cur = 0;
    28.             _for(j, 0, 25)
    29.                 if(!ban[j][x - 'a']) 
    30.                     cur = max(cur, dp[j] + 1);
    31.             dp[x - 'a'] = max(dp[x - 'a'], cur);
    32.         }
    33.     }
    34.  
    35.     int mx = 0;
    36.     _for(i, 0, 25) mx = max(mx, dp[i]);
    37.     printf("%d\n", mx + ans);
    38.  
    39.     return 0;
    40. }

    J Gachapon（构造）

    从样例猜构造方法，可惜猜的是最低为1/2  其实把最低的换成n就对了

    这个分数加减比较复杂，考虑容易约分的形式

    也就是1/ 2  *2/3  * 3/4……

    即(1-1/2)(1-1/3)……

    所以可以考虑构造这种分数

    设初始为A，然后1/m到1/n

    然后一波激情运算，注意一些算式可以表示为一个变量，这样推起来方便，因为最终目的是为了写程序。

    注意到变量只有m和A，于是可以解出m和A关系

    最后枚举m算出A，看A是否满足条件即可

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. ll x, y;
    8.  
    9. ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
    10.  
    11. int main()
    12. { 
    13.     scanf("%lld%lld", &x, &y);
    14.  
    15.     ll sum = 0;
    16.     _for(i, 2, x - 1) sum += i;
    17.  
    18.     _for(m, x - 1, 1e9)
    19.     {
    20.         ll n = m - x + 3;
    21.         ll t = sum + (n - 1) * x;
    22.  
    23.         ll up = m * y - t;
    24.         ll down = m - t;
    25.  
    26.         if(up < 0 && down < 0) up = -up, down = -down;
    27.         if(up * down <= 0 || up >= down) continue;
    28.         ll d = gcd(up, down);
    29.         up /= d;
    30.         down /= d;
    31.  
    32.         if(down > 10000) continue;
    33.  
    34.         printf("%lld %lld\n", up, down);
    35.         for(ll i = m; i >= n; i--) printf("1 %lld\n", i);
    36.         puts("1 1");
    37.         break;
    38.     }
    39.  
    40.     return 0;
    41. }

    抽卡（概率）

    入门题，只需要算一下不可能的概率，然后用1减去就行

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int mod = 1e9 + 7;
    8. const int N = 1e5 + 10;
    9. int a[N], b[N], n;
    10.  
    11. ll binpow(ll a, ll b)
    12. {
    13.     ll res = 1;
    14.     for(; b; b >>= 1)
    15.     {
    16.         if(b & 1) res = res * a % mod;
    17.         a = a * a % mod;
    18.     }
    19.     return res;
    20. }
    21.  
    22. ll inv(ll x) { return binpow(x, mod - 2); }
    23.  
    24. int main()
    25. { 
    26.     scanf("%d", &n);
    27.     _for(i, 1, n) scanf("%d", &a[i]);
    28.     _for(i, 1, n) scanf("%d", &b[i]);
    29.  
    30.     ll ans = 1;
    31.     _for(i, 1, n)
    32.         ans = ans * (a[i] - b[i]) % mod * inv(a[i]) % mod;
    33.     printf("%lld\n", (1 - ans + mod) % mod);
    34.  
    35.     return 0;
    36. }

    周二

    一袋小球（概率dp）

    讨论一下什么情况先手能赢即可。

    注意边界条件

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 1e3 + 10;
    7. double dp[N][N];
    8. int A, B;
    9.  
    10. int main()
    11. { 
    12.     scanf("%d%d", &A, &B);
    13.     _for(i, 1, A) dp[i][0] = 1;
    14.     
    15.     _for(a, 1, A)
    16.         _for(b, 1, B)
    17.         {
    18.             dp[a][b] = 1.0 * a / (a + b);
    19.             if(b >= 3) dp[a][b] += 1.0 * b / (a + b) * (b - 1) * (b - 2)
    20.                     / (a + b - 1) / (a + b - 2) * dp[a][b - 3];
    21.             if(a >= 1 && b >= 2)
    22.                 dp[a][b] += 1.0 * b / (a + b) * (b - 1) / (a + b - 1) * a
    23.                             / (a + b - 2) * dp[a - 1][b - 2];
    24.         }
    25.     printf("%.10f\n", dp[A][B]);
    26.  
    27.     return 0;
    28. }

    P2473 [SCOI2008] 奖励关（状压dp）

    记住概率顺推，期望逆推。

    首先n很小，马上想到状压dp

    如果是正常的思路，那么就是对于当前S，枚举它的子集转移过来

    但是这题要算期望，怎么处理呢？这题有一些条件限制，满足si才能买，这使得概率并不均匀，考虑起来很复杂

    因此反过来处理，也就是逆推，就很好处理

    在当前这个状态下，抽到哪一个东西的概率是均等的，所以就加上n种情况的结果，然后除以n即可。

    做期望的时候，逆推的思考方式是很方便的。

    此外，这题我开始在想最优策略是什么，其实意思就是dp取最大值，这样就是最优策略

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. int p[20], sta[20], n, k;
    7. double dp[110][1 << 15];
    8.  
    9. int main()
    10. { 
    11.     scanf("%d%d", &k, &n);
    12.     rep(i, 0, n)
    13.     {
    14.         scanf("%d", &p[i]);
    15.         int x;
    16.         while(scanf("%d", &x) && x) 
    17.             sta[i] |= 1 << (x - 1);
    18.     }
    19.  
    20.     for(int i = k; i >= 1; i--)
    21.         rep(S, 0, 1 << n)
    22.         {
    23.             rep(j, 0, n)
    24.             {
    25.                 if((S & sta[j]) == sta[j]) dp[i][S] += max(dp[i + 1][S], dp[i + 1][S | 1 << j] + p[j]);  //注意包含的写法
    26.                 else dp[i][S] += dp[i + 1][S];
    27.             }
    28.             dp[i][S] /= n;
    29.         }
    30.     printf("%.6f\n", dp[1][0]);   //有些题目固定说保留几位小数，要注意
    31.  
    32.     return 0;
    33. }

    Accumulation Degree（换根dp+细节）

    这题的细节搞了我好久

    首先对于流量，按照题目的从根到各个叶子，流量会分叉比较难思考，所以我们反过来，看作从叶子到根的流量

    用dp[i]表示以i为根的子树的最大流量

    那么dp[u] = sigma min(w, dp[v])

    特例是如果u是叶子的话，dp[u] = 0同时v是叶子的话，取w而不是min(w, dp[v])

    所以儿子v的贡献是需要分类讨论的，而当换根的时候也会出现这种情况，v可能是儿子，u可能变成儿子，如果它们成儿子时是叶子的话，贡献就不一样。

    所以干脆写一个函数min(w, v == 0 ? 1e9 : v) 来计算贡献

    这样就非常清晰了，不用考虑哪些度数为1的情况

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 2e5 + 10;
    7. vector<pair<int, int>> g[N];
    8. int dp[N], f[N], n;
    9.  
    10. int val(int w, int v)
    11. {
    12.     return min(w, v == 0 ? (int)1e9 : v);
    13. }
    14.  
    15. void dfs(int u, int fa)
    16. {
    17.     dp[u] = 0;
    18.     for(auto x: g[u])
    19.     {
    20.         int v = x.first, w = x.second;
    21.         if(v == fa) continue;
    22.         dfs(v, u);
    23.         dp[u] += val(w, dp[v]);
    24.     }
    25. }
    26.  
    27. void dfs2(int u, int fa)
    28. {
    29.     for(auto x: g[u])
    30.     {
    31.         int v = x.first, w = x.second;
    32.         if(v == fa) continue;
    33.         f[v] = dp[v] + val(w, f[u] - val(w, dp[v]));
    34.         dfs2(v, u);
    35.     }
    36. }
    37.  
    38. int main()
    39. { 
    40.     int T; scanf("%d", &T);
    41.     while(T--)
    42.     {
    43.         scanf("%d", &n);
    44.         _for(i, 1, n) g[i].clear();
    45.         _for(i, 1, n - 1)
    46.         {
    47.             int u, v, w;
    48.             scanf("%d%d%d", &u, &v, &w);
    49.             g[u].push_back({v, w});
    50.             g[v].push_back({u, w});
    51.         }
    52.  
    53.         dfs(1, 0);
    54.         f[1] = dp[1];
    55.         dfs2(1, 0);
    56.  
    57.         int res = 0;
    58.         _for(i, 1, n) res = max(res, f[i]);
    59.         printf("%d\n", res);
    60.     }
    61.  
    62.     return 0;
    63. }

    周三

    [NOIP2017]宝藏（状压dp）

    好题啊

    n这么小肯定是状压或者搜索，要马上反应过来

    这题的难点在于怎么处理这个生成树

    发现价值的计算只与层数有关，所以我们并不关心具体的构造，只需要关心层数

    那么用dp[S][i]表示当前生成树已选的点为S，有i层的最小花费

    要转移的话，就枚举第i层选哪些点，这些点的花费全部算为乘上i

    注意，这样虽然会把答案算偏大，但是一定包括了正确答案

    那么转移方程就是dp[S][i] = min(dp[S0][i - 1] + cost(S0, S))

    S0是S的子集，枚举状态，再枚举它的子集，时间复杂度是3^n，不是4^n

    考虑这里的cost(S0,S)该怎么算，显然可以枚举多出来的点向S0中的点连边

    这个东西可以预处理，不写在循环中而加快速度。

    预处理是3 ^ n * n ^ 2  dp是3 ^ n * n 花费主要在预处理

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. int n, m, g[20][20], f[1 << 12][1 << 12], dp[1 << 12][20];
    7.  
    8. int main()
    9. { 
    10.     memset(g, 0x3f, sizeof g);
    11.     scanf("%d%d", &n, &m);
    12.     while(m--)
    13.     {
    14.         int u, v, w;
    15.         scanf("%d%d%d", &u, &v, &w);
    16.         u--; v--;
    17.         g[u][v] = g[v][u] = min(g[u][v], w);
    18.     }
    19.  
    20.     memset(f, 0x3f, sizeof f);
    21.     rep(S, 0, 1 << n)
    22.         for(int S0 = S; S0; S0 = (S0 - 1) & S)
    23.         {
    24.             int res = 0;
    25.             rep(j, 0, n)
    26.                 if((S & (1 << j)) && !(S0 & (1 << j)))
    27.                 {
    28.                     int cur = 1e9;
    29.                     rep(k, 0, n)
    30.                         if(S0 & (1 << k))
    31.                             cur = min(cur, g[j][k]);
    32.                     if(cur == 1e9) 
    33.                     {
    34.                         res = 1e9;
    35.                         break;
    36.                     }
    37.                     else res += cur;
    38.                 }
    39.             f[S0][S] = res;
    40.         }
    41.  
    42.     memset(dp, 0x3f, sizeof dp);
    43.     rep(i, 0, n) dp[1 << i][0] = 0;
    44.     rep(i, 1, n - 1)
    45.         rep(S, 0, 1 << n)
    46.             for(int S0 = S; S0; S0 = (S0 - 1) & S)
    47.                 if(f[S0][S] < 1e9)
    48.                     dp[S][i] = min(dp[S][i], dp[S0][i - 1] + f[S0][S] * i);
    49.     
    50.     int ans = 1e9;
    51.     _for(i, 0, n - 1) ans = min(ans, dp[(1 << n) - 1][i]);
    52.     printf("%d\n", ans);
    53.  
    54.     return 0;
    55. }

    刷野（区间dp）

    从数据范围可以看出是区间dp

    但是这个区间dp有点技巧

    在一个区间里面选一个野怪时，它的左右边是谁呢？

    不一定，所以我们就把左边的杀完，右边的杀完，在杀当前这个，这样它的左边是l-1,右边是r+1

    人为规定了这个顺序后，就可以计算了，而且这个规定也没有很特殊，可以包含所有情况

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 500 + 10;
    7. int dp[N][N], a[N], b[N], n;
    8.  
    9. int main()
    10. { 
    11.     scanf("%d", &n);
    12.     _for(i, 1, n) scanf("%d", &a[i]);
    13.     _for(i, 1, n) scanf("%d", &b[i]);
    14.     
    15.     memset(dp, 0x3f, sizeof dp);
    16.     _for(i, 1, n) dp[i][i] = a[i] + b[i - 1] + b[i + 1];
    17.     _for(len, 2, n)
    18.         _for(l, 1, n)
    19.         {
    20.             int r = l + len - 1;
    21.             if(r > n) break;
    22.             _for(k, l + 1, r - 1)
    23.                 dp[l][r] = min(dp[l][r], dp[l][k - 1] + dp[k + 1][r] + a[k] + b[l - 1] + b[r + 1]);
    24.             dp[l][r] = min(dp[l][r], a[l] + dp[l + 1][r] + b[l - 1] + b[r + 1]);
    25.             dp[l][r] = min(dp[l][r], a[r] + dp[l][r - 1] + b[l - 1] + b[r + 1]);
    26.         }
    27.     printf("%d\n", dp[1][n]);
    28.  
    29.     return 0;
    30. }

    [HAOI2011]PROBLEM A(dp)

    首先转化一下，求最多右多少人说了真话，这样比较容易处理。

    首先可以转化成排名区间，我一开始想的是，只要两个区间有交集就是冲突的，所以直接按照右端点排序贪心选取即可，然后就WA了

    关键点在于一个特例，如果右多个相同的区间，且它们长度大于1，那么根据这道题，就是合法的！我就是这点没考虑到

    考虑到这点后，就给区间附上了权值，且区间权值的最大值就是区间长度。

    那么问题就变成了每个区间有权值，选不相交的区间使得权值最大

    这个可以dp解决，dp[i]表示1~i的最优值，然后枚举右端点为i的区间转移即可

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 1e5 + 10;
    7. map<pair<int, int>, int> mp;
    8. vector<pair<int, int>> g[N];
    9. int dp[N], n, ans;
    10.  
    11. int main()
    12. { 
    13.     scanf("%d", &n);
    14.     _for(i, 1, n)
    15.     {
    16.         int a, b;
    17.         scanf("%d%d", &a, &b);
    18.         if(a + b < n) mp[{b + 1, n - a}]++;
    19.     }
    20.     for(auto x: mp)
    21.     {
    22.         int l = x.first.first, r = x.first.second, v = x.second;
    23.         g[r].push_back({l, min(r - l + 1, v)});
    24.     }
    25.  
    26.     _for(i, 1, n)
    27.     {
    28.         dp[i] = dp[i - 1];
    29.         for(auto x: g[i])
    30.         {
    31.             int j = x.first, v = x.second; 
    32.             dp[i] = max(dp[i], v + dp[j - 1]);
    33.         }
    34.     }
    35.     printf("%d\n", n - dp[n]);
    36.  
    37.     return 0;
    38. }

    Min酱要旅行（背包拓展）

    逆向思考，不取i的，那就把一定取i的去掉

    那么问题就转为如何求体积为j，一定取i的方案数

    那么就是j-w[i]后，一定不取i的方案数

    那么干脆就把g[j]表示为体积为j，一定不取i的方案数

    有g[j] = f[j] - g[j - w[i]]

    因此求出f之后，递推求出g数组即可

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 2500;
    7. int f[N], g[N], w[N], n, m;
    8.  
    9. int main()
    10. { 
    11.     scanf("%d%d", &n, &m);
    12.     _for(i, 1, n) scanf("%d", &w[i]);
    13.  
    14.     f[0] = 1;
    15.     _for(i, 1, n)
    16.         for(int j = m; j >= w[i]; j--)
    17.             f[j] = (f[j] + f[j - w[i]]) % 10;
    18.     
    19.     _for(i, 1, n)
    20.     {
    21.         _for(j, 0, m)  //注意体积从0开始枚举
    22.         {
    23.             g[j] = f[j];
    24.             if(j - w[i] >= 0) g[j] = (g[j] - g[j - w[i]] + 10) % 10;
    25.         }
    26.         _for(j, 1, m) printf("%d", g[j]);
    27.         puts("");
    28.     }
    29.  
    30.     return 0;
    31. }

    周四

    管道取珠（思维+dp）

    这题的关键在于平方和

    考虑其物理意义

    即两个一模一样的装置，结果相同的方案数

    比如一个装置中某个方案为ai种，另一个相同的装置此方案也是ai

    那么相同的就是ai^2

    那么就根据这个dp

    dp[i][j][k][l]表示第一个装置上面出了i个，下面出了j个，第二个装置上面k个下面l个时相同的方案数

    那么如果a[i] == a[k] dp[i][j][k][l] += dp[i - 1][j][k - 1][l]

    这样是n的四次方的

    但是发现l是多余的，因为i+j=k+l

    所以可以优化掉一个维度

    初始化为dp[0][0][0] = 1  转移时从0开始枚举，注意负数情况 

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 500 + 10;
    7. const int mod = 1024523;
    8. int dp[N][N][N], n, m;
    9. char a[N], b[N];
    10.  
    11. int main()
    12. { 
    13.     scanf("%d%d%s%s", &n, &m, a + 1, b + 1);
    14.     reverse(a + 1, a + n + 1);
    15.     reverse(b + 1, b + m + 1);
    16.     
    17.     dp[0][0][0] = 1;
    18.     _for(i, 0, n)
    19.         _for(j, 0, m)
    20.             _for(k, 0, n)
    21.             {
    22.                 int l = i + j - k;
    23.                 if(i && k && a[i] == a[k]) dp[i][j][k] += dp[i - 1][j][k - 1];
    24.                 if(i && l && a[i] == b[l]) dp[i][j][k] += dp[i - 1][j][k];
    25.                 if(j && k && b[j] == a[k]) dp[i][j][k] += dp[i][j - 1][k - 1];
    26.                 if(j && l && b[j] == b[l]) dp[i][j][k] += dp[i][j - 1][k];
    27.                 dp[i][j][k] %= mod;
    28.             }
    29.     printf("%d\n", dp[n][m][n]);
    30.  
    31.     return 0;
    32. }

    周五

    打砖块（观察+dp）

    这题的关键点在于，看成一列一列的放，同时下一列的高度要大于等于当前这一列减去一

    发现无论怎么选都有这一个规律

    根据这个dp即可，一列一列来

    注意有一列什么都不放的情况

    最后统计答案要统计最后一列，因为中间有一些不合法的情况

    也可也从第n列从第1列，这样每个状态都是合法的

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 50 + 10;
    7. const int M = 500 + 10;
    8. int dp[N][N][M], a[N][N], sum[N][N], n, m;
    9.  
    10. int main()
    11. { 
    12.     scanf("%d%d", &n, &m);
    13.     _for(i, 1, n)
    14.         _for(j, 1, n - i + 1)
    15.             scanf("%d", &a[i][j]);
    16.  
    17.     _for(j, 1, n)
    18.         _for(i, 1, n - j + 1)
    19.             sum[j][i] = sum[j][i - 1] + a[i][j];
    20.    
    21.     memset(dp, -0x3f, sizeof dp);
    22.     _for(i, 0, n) dp[1][i][i] = sum[1][i];
    23.     _for(j, 1, n)
    24.         _for(i, 0, n - j + 1)
    25.             _for(l, max(i - 1, 0), n - j)
    26.                 _for(k, 0, m - l)
    27.                     dp[j + 1][l][k + l] = max(dp[j + 1][l][k + l], dp[j][i][k] + sum[j + 1][l]);
    28.     printf("%d\n", max(dp[n][0][m], dp[n][1][m]));
    29.                         
    30.     return 0;
    31. }

    周六

    [HAOI2010]最长公共子序列（dp+方案数）

    这题有很多点可以学习

    用g[i][j]表示前i个和前j个的最长公共子序列的个数

    可以先用dp转移完，然后再统计方案数

    由哪些状态可以转移过来，就转移哪些状态的方案数

    但是有一个特例，当dp[i][j] == dp[i - 1][j - 1]时，多的a[i]和b[j]并没有产生贡献

    这时g[i - 1][j - 1]给了g[i][j - 1],再给g[i][j]，同时g[i - 1][j - 1]给了g[i - 1][j] 再给g[i][j]

    重复计算了，所以要减去g[i - 1][j - 1]

    此外，此题限制空间，需要滚动数组。

    滚动数组的时候要记得当前的数组是已经有值的，要处理一下，要么覆盖要么初始化为0，也就是清空。

    g数组的初始化为长度为0的最长公共子序列的方案数为1。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 5000 + 10;
    8. const int mod = 1e8;
    9. char a[N], b[N];
    10. int dp[2][N], g[2][N];
    11.  
    12. int main()
    13. { 
    14.     scanf("%s%s", a + 1, b + 1);
    15.     int lena = strlen(a + 1) - 1;
    16.     int lenb = strlen(b + 1) - 1;
    17.  
    18.     g[1][0] = 1;
    19.     _for(i, 0, lenb) g[0][i] = 1;
    20.     _for(i, 1, lena)
    21.     {
    22.         int cur = i % 2, pre = (i - 1) % 2;
    23.         _for(j, 1, lenb)
    24.         {
    25.             dp[cur][j] = max(dp[pre][j], dp[cur][j - 1]);
    26.             if(a[i] == b[j]) dp[cur][j] = max(dp[cur][j], dp[pre][j - 1] + 1);
    27.             g[cur][j] = 0;
    28.  
    29.             if(a[i] == b[j] && dp[pre][j - 1] + 1 == dp[cur][j]) g[cur][j] += g[pre][j - 1];
    30.             if(dp[cur][j] == dp[pre][j]) g[cur][j] += g[pre][j];
    31.             if(dp[cur][j] == dp[cur][j - 1]) g[cur][j] += g[cur][j - 1];
    32.             if(dp[cur][j] == dp[pre][j - 1]) g[cur][j] -= g[pre][j - 1];
    33.             
    34.             g[cur][j] = (g[cur][j] + mod) % mod;
    35.         }
    36.     }
    37.     printf("%d\n%d\n", dp[lena % 2][lenb], g[lena % 2][lenb]);
    38.                         
    39.     return 0;
    40. }

    [AHOI2009]CHESS 中国象棋（dp求方案数）

    数据比较小的时候可以用三进制状压做，和之前做一个八皇后方案数是类似的

    但是题目给的是100，就无法状压了

    考虑简化状态，实际上只需要考虑有多少列放了1个，多少放了0个，多少放了2个即可

    用dp[i][j][k]表示前i行，有j列放了0个，k列放了1个

    对于放了2个即m-j-k

    那么枚举当前行怎么放即可

    为了思考的方便，可以写成往后推的dp。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int mod = 9999973;
    8. const int N = 110;
    9. ll dp[N][N][N];
    10. int n, m;
    11.  
    12. int main()
    13. { 
    14.     scanf("%d%d", &n, &m);
    15.     dp[1][m][0] = 1;
    16.     dp[1][m - 1][1] = m;
    17.     dp[1][m - 2][2] = m * (m - 1) / 2;
    18.  
    19.     _for(i, 1, n - 1)
    20. 		_for(j, 0, m)     // 0
    21. 			_for(k, 0, m)  // 1
    22. 			{
    23. 				int l = m - j - k; // 2
    24. 				if(l < 0) break;
    25.  
    26. 				//一个都不放
    27. 				dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % mod;
    28.  
    29. 				//放一个
    30. 				//放在0列
    31. 				if(j > 0) dp[i + 1][j - 1][k + 1] = (dp[i + 1][j - 1][k + 1] + dp[i][j][k] * j % mod) % mod;
    32. 				//放在1列
    33. 				if(k > 0) dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k] * k % mod) % mod;
    34.  
    35. 				//放两个
    36. 				//1个0列 1个0列
    37. 				if(j > 1) dp[i + 1][j - 2][k + 2] = (dp[i + 1][j - 2][k + 2] + dp[i][j][k] * (j * (j - 1) / 2) % mod) % mod;
    38. 				//1个1列 1个0列
    39. 				if(j > 0 && k > 0) dp[i + 1][j - 1][k] = (dp[i + 1][j - 1][k] + dp[i][j][k] * j * k % mod) % mod;
    40. 				//1个1列 1个1列
    41. 				if(k > 1) dp[i + 1][j][k - 2] = (dp[i + 1][j][k - 2] + dp[i][j][k] * (k * (k - 1) / 2) % mod) % mod;
    42. 			}
    43. 	
    44. 	ll ans = 0;
    45. 	_for(j, 0, m)    
    46. 		_for(k, 0, m)  
    47. 		{
    48. 			int l = m - j - k; 
    49. 			if(l < 0) break;
    50. 			ans = (ans + dp[n][j][k]) % mod;
    51. 		}
    52. 	printf("%lld\n", ans);
    53.     
    54.     return 0;
    55. }

    [SCOI2009]粉刷匠（dp）

    读完题就知道是一个分组背包，关键是怎么求一行。

    我一开始卡住在于觉得涂的时候只是涂一部分，其实可以发现把全部涂满的方案一定是最优方案之一，因为不涂白不涂，有了这一点就容易dp了

    f[i][j]表示用j次把前i块涂满的最多正确的值，每次枚举最后一次涂多少就可以。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 60;
    7. const int M = 2500 + 10;
    8. int f[N][N], a[N], s[N], dp[M], n, m, T;
    9. vector<pair<int, int>> ve[N];
    11. void deal(int x)
    12. {
    13. 	memset(f, 0, sizeof f);
    14. 	_for(i, 1, m)
    15. 		_for(j, 1, i)
    16. 			_for(k, 1, i)
    17. 				f[i][j] = max(f[i][j], f[k - 1][j - 1] + max(s[i] - s[k - 1], (i - k + 1) - (s[i] - s[k - 1])));
    18. 	_for(j, 1, m) ve[x].push_back({j, f[m][j]});
    19. }
    20.  
    21. int main()
    22. { 
    23.     scanf("%d%d%d", &n, &m, &T);
    24. 	_for(i, 1, n)
    25. 	{
    26. 		_for(j, 1, m) scanf("%1d", &a[j]), s[j] = s[j - 1] + a[j];
    27. 		deal(i);
    28. 	}
    29. 	
    30. 	_for(i, 1, n)
    31. 		for(int j = T; j >= 0; j--)
    32. 			for(auto x: ve[i])
    33. 			{
    34. 				int w = x.first, v = x.second;
    35. 				if(j >= w) dp[j] = max(dp[j], dp[j - w] + v);
    36. 			}
    37. 	printf("%d\n", dp[T]);
    38.  
    39.     return 0;
    40. }

    区间价值（dp）

    用f[i]表示区间长度为i的答案

    观察怎么转移 首先最后一个会消失，所以要求一个后缀不同数字的个数，可以O(n)求

    然后发现，对于一个区间增加，要贡献1就要使得区间中没有这个数

    转化一下，也就是这个数和前一个相同的差要大于等于i

    那么我们可以求每个数与前面的数的差等于i的值，然后求一个后缀和使得大于等于i

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 1e6 + 10;
    8. int a[N], vis[N], dif[N], pre[N], k[N], cnt, n;
    9. ll f[N];
    10.  
    11. int main()
    12. { 
    13. 	scanf("%d", &n);
    14. 	_for(i, 1, n) scanf("%d", &a[i]);
    15.  
    16. 	for(int i = n; i >= 1; i--)
    17. 	{
    18. 		if(!vis[a[i]])
    19. 		{
    20. 			vis[a[i]] = 1;
    21. 			cnt++;
    22. 		}
    23. 		dif[n - i + 1] = cnt;
    24. 	}
    25.  
    26. 	_for(i, 1, n)
    27. 	{
    28. 		k[i - pre[a[i]]]++;
    29. 		pre[a[i]] = i;
    30. 	}
    31. 	for(int i = n - 1; i >= 1; i--) k[i] += k[i + 1];
    32.  
    33. 	f[1] = n;
    34. 	_for(i, 2, n) f[i] = f[i - 1] + k[i] - dif[i - 1];
    35. 	
    36. 	int q; scanf("%d", &q);
    37. 	_for(i, 1, q)
    38. 	{
    39. 		int x; scanf("%d", &x);
    40. 		printf("%lld\n", f[x]);
    41. 	}
    42.  
    43.     return 0;
    44. }

  • 相关阅读:
    abc 321 c
    优化预算管理流程：Web端实现预算编制的利器
    支付宝支付功能实现
    怎么将pdf转换成word？
    （附源码）springboot社区文明养宠平台 毕业设计 231609
    北斗通信模块 北斗gps模块 北斗通信终端DTU
    「重学JS」你真的懂数据类型吗?
    HAProxy（一）
    【自用】Linux-CentOS7安装配置jdk1.8
    使用 JavaScript 和 CSS 的简单图像放大镜
  • 原文地址：https://blog.csdn.net/qq_34416123/article/details/126929589