Namomo-Camp-2021-day1-DP

2021-02-09 分类 Namomo Camp 2021 作者 Hile_Meow ~12.18K 字

luoguP2612

题意

设一个排列的权值为相邻两数差的绝对值之和，求长度为$n$的随机排列权值不小于$m$的概率（$n\le100$）

题解

考虑一个填完的排列中每个数对答案的贡献，

设当前填的数为$b$，其前后的数分别为$a$和$c$，则有三种情况：

当$[a<b\land c<b]==1$时，答案要加上$|a-b|+|b-c|=2\times b-a-c$，$b$对答案的贡献为$2\times b$
当$[a<b\oplus c<b]==1$时，答案要加上$|a-b|+|b-c|=|a-c|$，$b$对答案的贡献为$0$
当$[a>b\land c>b]==1$时，答案要加上$|a-b|+|b-c|=a+c-2\times b$，$b$对答案的贡献为$-2\times b$

为了消去绝对值的影响，我们从小到大填数。

在从小到大填数时，出现情况1说明填当前位置时左右都非空，出现情况2说明左右有一个非空，出现情况3说明左右都为空，而且如果填在两端要特殊处理一下。

考虑用$f(i,j,k,t)$表示已经填了$i$个数，构成了$j$个连续段，答案为$k$，有$t$个端点填了数的方案数，其中$i\in[0,n],j\in[0,\lceil\frac{n}{2}\rceil],k\in[-4500,4500],t\in[0,2]$，

如果不填在两端，根据上面的情况，有三种转移方式：

$f(i,j,k,l)\longrightarrow f(i+1,j,k,l)$

$f(i,j,k,l)\longrightarrow f(i+1,j+1,k-2\times i,l)$

$f(i,j,k,l)\longrightarrow f(i+1,j-1,k+2\times i,l)$

如果填在两端，有两种转移方式（端点旁边是否有数）：

$f(i,j,k,l)\longrightarrow f(i,j,k+i,l+1)$

$f(i,j,k,l)\longrightarrow f(i,j+1,k-i,l+1)$

转移时注意乘上可以选择的方案数。

代码

这题着实恶心，得面向数据范围编程，$k\le8$用long double，否则用__float128才能过，~~所以写的又臭又长~~，这里只放了dp部分的代码

f[0][0][D][0] = 1;
for (int i = 1; i <= n; i++) {
    int from = ~i & 1, to = i & 1;
    memset(f[to], 0, sizeof f[to]);
    for (int j = 0; j <= min(i - 1, m); j++) {
        for (int k = 0; k < M; k++) {
            for (int t = 0; t < 3; t++) {
                ff = f[from][j][k][t];
                //分别对应上面的转移方式
                if (j)f[to][j][k][t] += ff * (2 * j - t);
                if (k - 2 * i >= 0)f[to][j + 1][k - 2 * i][t] += ff * (j + 1 - t);
                if (j > 1 && k + 2 * i < M)f[to][j - 1][k + 2 * i][t] += ff * (j - 1);
                if (t < 2 && j && k + i < M)f[to][j][k + i][t + 1] += ff * (2 - t);
                if (t < 2 && k - i >= 0)f[to][j + 1][k - i][t + 1] += ff * (2 - t);
            }
        }
    }
}

CF908G

题意

$S(n)$为$n$所有位数非降序排列后的数值，求$\sum_{i=1}^X S(i)\mod 10^9+7$（$X\le10^{700}$）

题解

~~应该是自己做过的第三道数位dp，数位dp好难啊~~

看这个数据范围，$10^{700}$，显然是数位dp，但有一说一确实挺怪的，

河里猜测，状态数应该是$700\times 700\times 10\times x$，

~~然后就不会了（~~

看了别人的题解，发现其实还是挺好懂的，

举个例子，$S(114514)$可以拆成三部分的贡献：$S(114514)=111445=111111+111+1$（其实是九部分，对应$1-9$），

因此可以分别枚举每个位置产生的贡献之和，然后分别加起来，

具体来说就是

没写完

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 710;
const int MOD = 1e9 + 7;
string X;
ll f[N][10][N][2], ans, p10[N];
ll dp(int t, int num, int m, int lim) {
    if (m < 0)return 0;
    if (t == X.size())return !m;
    if (f[t][num][m][lim] != -1) {
        return f[t][num][m][lim];
    }
    ll res = 0;
    if (lim) {
        for (int i = 0; i <= X[t] - '0'; i++) {
            res = (res + dp(t + 1, num, m - (i >= num), i == X[t] - '0')) % MOD;
        }
    } else {
        for (int i = 0; i <= 9; i++) {
            res = (res + dp(t + 1, num, m - (i >= num), 0)) % MOD;
        }
    }
    return f[t][num][m][lim] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> X;
    memset(f, -1, sizeof f);
    p10[0] = 1;
    for (int i = 1; i < N; i++)p10[i] = p10[i - 1] * 10 % MOD;
    for (int i = 1; i < N; i++)p10[i] = (p10[i - 1] + p10[i]) % MOD;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= X.size(); j++) {
            // cout << i << " " << j << ": " << (p10[j - 1]*dp(0, i, j, 1)) << "\n";
            ans = (ans + (p10[j - 1]) * dp(0, i, j, 1) % MOD) % MOD;
        }
    }
    cout << ans;
}

CF1142D

题意

给定$n$个非降序排列的数组，第$i$个数组长度为$t_i$，每次操作可以取出任意数组最左边的数（相当于删除）并加到答案里，求$k$次操作后的最大答案（$n,k\le3000$）

题解

一个显然的结论是，最多只有一个数组被取数但没有被全取完，利用反证法容易证明。

根据这个结论，最暴力的办法就是考虑枚举没选中的数组然后对其他的做一遍背包，

但是这是$O(n^2k)$的，显然会超时，s思考后发现，在枚举不同数组进行背包的时候，只有两个物品不同，其他$n-2$个都是一样的，

因此可以考虑如何重复使用这些物品，起码要优化到$O(nk\log n)$才行，

既然带了个$\log$，大概率要用线段树，

朝着这个方向想想，结果就出来了，

我们可以在线段树节点$(i,l,r)$上用$f(i)$来储存除了$l,r$数组之外的所有物品做$01$背包后的结果，

这样就把$n^2k$枚举时的加减物品变成了从根到叶的加物品操作，

叶节点即为之前所枚举的没有被全取完的数组，复杂度$O(nk\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3030;
const int MOD = 1e9 + 7;
const ll INF = 4e18;
vector<ll> a[N], f[N], now;
int n, k, t[N];
ll sum[N], ans;
vector<ll> dp(vector<ll> &v, int l, int r) {
    vector<ll> res = v;
    for (int i = l; i <= r; i++) {
        for (int j = k; j >= a[i].size(); j--) {
            res[j] = max(res[j], res[j - a[i].size()] + sum[i]);
        }
    }
    return res;
}
void solve(int l, int r) {
    ll res = 0;
    if (l == r) {
        ans = max(ans, now[k]);
        for (int i = 1; i <= min(k,(int)a[l].size()); i++) {
            res += a[l][i - 1];
            ans = max(ans, res + now[k - i]);
        }
        return;
    }
    int mid = l + r >> 1;
    vector<ll> tmp = now;
    now = dp(tmp, mid + 1, r);
    solve(l, mid);
    now = dp(tmp, l, mid);
    solve(mid + 1, r);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    now.resize(k + 1, -INF);
    now[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        for (int j = 1, tt; j <= t[i]; j++) {
            cin >> tt;
            a[i].push_back(tt);
            sum[i] += tt;
        }
    }
    solve(1, n);
    cout << ans;
}

300iq Contest 3 C

题意

在写了在写了

题解

在写了在写了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3030;
const int INF = 0x3f3f3f3f;
int n, m;
char s[N][N];
ll ans, cnt;
int a[N][N], b[N][N];
vector<int> ve[N << 1];
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> s[i][j];
            cnt += s[i][j] == '.';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] |= a[i - 1][j] | a[i][j - 1];
            a[i][j] |= i == 1 && j == 1;
            a[i][j] &= s[i][j] == '.';
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 1; j--) {
            b[i][j] |= b[i + 1][j] | b[i][j + 1];
            b[i][j] |= i == n && j == m;
            b[i][j] &= s[i][j] == '.';
        }
    }
    if (!a[n][m]) {
        cout << cnt*(cnt - 1) / 2;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j] || !b[i][j]) {
                s[i][j] = '*';
            } else {
                ve[i + j].push_back(i);
            }
        }
    }
    for (int i = 2; i <= n + m; i++) {
        if (ve[i].size() == 1)ans += --cnt;
        else if (ve[i].size() == 2)ans++;
        if (ve[i].size())sort(ve[i].begin(), ve[i].end());
    }
    for (int i = 2; i <= n + m; i++) {
        if (ve[i].size() == 1)continue;
        int l = ve[i][1], r = ve[i].back();
        for (int j = i + 1; j <= n + m; j++) {
            if (s[l][j - l] != '.')l++;
            if (s[r + 1][j - (r + 1)] == '.')r++;
            if (l == r && ve[j].size() != 1)ans++;
        }
    }
    for (int i = 2; i <= n + m; i++) {
        if (ve[i].size() == 1)continue;
        int l = ve[i][0], r = ve[i][ve[i].size() - 2];
        for (int j = i + 1; j <= n + m; j++) {
            if (s[l][j - l] != '.')l++;
            if (s[r + 1][j - (r + 1)] == '.')r++;
            if (l == r && ve[j].size() != 1)ans++;
        }
    }
    cout << ans;
}

CF729F

题意

给定一长度为$n$的数组，$A$和$B$分别从左右端取数字加到自己身上，设$A,B$的分数分别为$W_A,W_B$，$S=W_A-W_B$，$A$想让$S$更大，$B$想让$S$更小，$A,B$都会采取最优策略，求最终$S$的值（$n\le4000$）

题解

在写了在写了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4040;
const int M = 66;
const int INF = 0x3f3f3f3f;
int n;
int a[N], s[N];
int f[N][M << 1][M][2];
bool vis[N][M << 1][M][2];
int sum(int l, int r) {
    return s[r] - s[l - 1];
}
int dp(int x, int y, int z, bool v) {
    int res = v ? INF : -INF, l = x, r = n + 1 - (x - (y - M));
    if (vis[x][y][z][v])return f[x][y][z][v];
    vis[x][y][z][v] = 1;
    for (int k = z; k <= z + 1 && k <= r - l - 1; k++) {
        if (v)res = min(res, dp(x, y - k, k, !v) - sum(r - k, r - 1));
        else res = max(res, dp(x + k, y + k, k, !v) + sum(l + 1, l + k));
    }
    if (abs(res) == INF)res = 0;
    return f[x][y][z][v] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    cout << dp(0, M, 1, 0);
}

2019CCPC秦皇岛G

题意

在写了在写了

题解

在写了在写了

代码

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 14;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
int n, a[N][N], f[1 << 24];
char s[N][N];
vector<int> b, w;
vector<pair<int, int>> pb, pw;
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%s", s[i] + 1);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        for (int i = 0; i < (1 << n + n); i++) {
            f[i] = INF;
        }
        int ed = (1 << n) - 1, st = (1 << n + n) - 1 - ed;
        f[st] = 0;
        for (int x = st; x >= ed; x--) {
            if (__builtin_popcount(x) != n)continue;
            int y, A = 0, B = 1;
            b.clear();
            w.clear();
            pb.clear();
            pw.clear();
            if (x & 1)B++;
            else A++;
            for (int i = 1; i < n + n; i++) {
                if (!((x >> i - 1) & 1) && ((x >> i) & 1)) {
                    if (s[A][B] == 'B') {
                        b.push_back(i);
                        pb.push_back({A, B});
                    } else if (s[A][B] == 'W') {
                        w.push_back(i);
                        pw.push_back({A, B});
                    }
                    y = x ^ (1 << i) ^ (1 << i - 1);
                    f[y] = min(f[y], f[x] + a[A][B]);
                }
                if ((x >> i) & 1)B++;
                else A++;
            }
            for (int i = 0; i < b.size(); i++) {
                for (int j = 0; j < w.size(); j++) {
                    y = x ^ (1 << b[i]) ^ (1 << b[i] - 1) ^ (1 << w[j]) ^ (1 << w[j] - 1);
                    f[y] = min(f[y], f[x] + abs(a[pb[i].first][pb[i].second] - a[pw[j].first][pw[j].second]));
                }
            }
        }
        printf("%d\n", f[ed]);
    }
}

[ ] 2020ICPC上海F
[ ] CF1428G
[ ] CF1383C
[ ] 2018CCPC吉林
[ ] DTOJ4632（没找到链接）

Hile_Meow's Blog

Namomo-Camp-2021-day1-DP

luoguP2612

CF908G

CF1142D

300iq Contest 3 C

CF729F

2019CCPC秦皇岛G

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

Hile_Meow's Blog

luoguP2612

CF908G

CF1142D

300iq Contest 3 C

CF729F

2019CCPC秦皇岛G

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可