日记 - 伊埃斯的博客站

上午

今天不用考试，所以是个补专题的好日子。

P4363 [九省联考 2018] 一双木棋 chess

我们先来看看一组我搓的样例：

这是初始状态，红色的格子表示下一步能选什么。

这是选了一个的状态

这是选了两个的状态
我们可以发现，在题目的限制下，黑色的轮廓线总是向上或者向右，如初始状态下就是 上上上上右右右右，第二种就是 上上上右上右右右 。这能发现什么，这不就能状压了吗？
我们设 $dp_{sta}$ 表示状态为 $sta$ 时的答案。其中： $sta$ 在二进制下的第 $i$ 位为 1 表示这个轮廓线为上。那么初始状态为 ((1 << n) - 1) << m 。那么如何转移呢？先暂且设下一个状态为 $nxt$ ，当前坐标为 $(x,y)$ ，那么有：

dp_{nxt} = \begin{cases} dp_{sta} + a_{x,y} & \text{该菲菲取} \\ dp_{sta} - b_{x,y} & \text{该牛牛取} \\ \end{cases}

然后重要的就是怎么求 $nxt$ 。我们看：这个点能取，也就是说他左上的轮廓线是 上右 。到状态里就是 ...01... 。那怎么判断呢？很简单，只需要按位与 0b11 。我们枚举到第 $i$ 位，当 (sta >> i) & 0b11 == 1 时，就说明满足条件了，我们就可以进行转移， $nxt$ 就是 sta ^ (0b11 << i) ，就是将那两位取反，变成 右上 。而结束状态就是 (1 << m) - 1 。但是我们怎么判断当前是该该菲菲取还是该牛牛取呢？一种是写判断小函数，但是我太懒也太蒻了，写不来。于是我写的记搜，把该谁取放在形参里传下去就可以了。
核心代码：

1
int dfs(int sta,int wh)//wh就是记录该谁取
2
{
3
    if (dp[sta] != inf)
4
        return dp[sta];
5
    dp[sta] = wh ? -inf : inf;
6
    int x = n,y = 0;
7
    for (int i = 0; i < n + m - 1; i++)
8
    {
9
        if ((1 << i) & sta)//这个if就是记录当前坐标的
10
            x --;
11
        else
12
            y ++;
13
        if (((sta >> i) & 0b11) != 1)//如果不可以转移
14
            continue;
15
        if (wh)//题解里说的转移
16
            dp[sta] = max(dp[sta],dfs(sta ^ (0b11 << i),wh ^ 1) + a[x][y]);
17
        else
18
            dp[sta] = min(dp[sta],dfs(sta ^ (0b11 << i),wh ^ 1) - b[x][y]);
19
    }
20
    return dp[sta];
21
}

UVA12983 The Battle of Chibi

solution
我们先想朴素的状态和转移：设 $dp_{i,j}$ 表示以 $a_i$ 结尾的长度为 $j$ 的子序列个数。那么有 $dp_{i,j} = \sum\limits_{k \in [1,i),a_k < a_i}dp_{k - 1,j - 1}$ 。但是我们发现：枚举状态就有 $\mathcal{O}(nm)$ 的，而转移又有 $\mathcal{O}(n)$ ，合起来就是 $\mathcal{O}(n^2m)$ ，这明显过不了啊。
我们考虑优化：我们发现 $dp_{i,j}$ 都是由 $dp_{x,j - 1}$ 转移而来的，所以最外层循环可以是 $j$ 。然后我们可以想到前缀和：以 $a_i$ 为下标，记录前 $i - 1$ 个数中 $a_k < a_i$ 的 $dp_{k,j - 1}$ 的前缀和，这个可以用树状数组。但是 $a_i$ 很大，要离散化。那么这样，我们成功的把dp优化到了 $\mathcal{O}(m \times n \log n)$ 。
核心代码：

1
for (int i = 1; i <= n; i++)
2
{
3
    cin >> a[i];
4
    apr[i] = a[i];
5
}
6
sort(apr + 1,apr + n + 1);
7
len = unique(apr + 1,apr + n + 1) - apr - 1;
8
memset(dp,0,sizeof dp);
9
for (int i = 1; i <= n; i++)
10
    dp[i][1] = 1;
11
for (int i = 1; i <= n; i++)
12
    a[i] = bound(a[i]);//bound用来求a[i]在apr[i]里的下标
13
for (int j = 2; j <= m; j++)
14
{
15
    memset(tree,0,sizeof tree);
16
    for (int i = 1; i <= n; i++)
17
    {
18
        dp[i][j] = que(a[i] - 1);//查询前缀和
19
        upd(a[i],dp[i][j - 1]);//记录dp[k][j - 1]的前缀和
20
    }
21
}
22
int ans = 0;
23
for (int i = 1; i <= n; i++)
24
    ans = (ans + dp[i][m]) % mod;

下午

P10978 Fence

solution
我们先来想朴素转移：设 $dp_{i,j}$ 表示第 $i$ 个工人刷到第 $j$ 块木板的最大收益。那么有三种情况：

不需要第 $i$ 个工人刷，答案为 $dp_{i - 1,j}$
第 $i$ 个工人不刷第 $j$ 块木板，答案为 $dp_{i,j - 1}$
第 $i$ 个工人刷第 $j$ 块木板，那么我们就枚举上个人所刷的区间的右端点 $k$ ，但是保证 $k + 1 \in [s_i - l_i,j]$ ，也就是下一块木板能被刷到。答案即为 $dp_{i - 1,k} + p_i \times (j - k)$

但是，我们发现这样的时间复杂度根本不可以，枚举状态是 $\mathcal{O}(nk)$ 的，转移还有一个 $\mathcal{O}(n)$ ，合起来就是 $\mathcal{O}(n^2k)$ 。这不行啊。
我们考虑优化。我们发现复杂度的瓶颈主要是第三种情况的转移，注意到第三种情况可以变成这个样子： $dp_{i - 1,k} - p_i \times k + p_i \times j$ 。但是，对于每一个 $i,j$ 来说， $p_i \times j$ 是不变的，那么我们就只用考虑最大的 $dp_{i - 1,k} - p_i \times k$ 。我们发现这个东西可以用单调队列维护。
code:

1
#include<iostream>
2
#include<algorithm>
3
#include<queue>
4
#define int long long
5
using namespace std;
6
int n,k;
7
int dp[105][16005];
8
struct Nahida{int l,p,s;}a[105];
9
bool operator<(const Nahida &x,const Nahida &y){return x.s < y.s;}
10
signed main()
11
{
12
    ios::sync_with_stdio(0);
13
    cin.tie(0);
14
    cout.tie(0);
15
    cin >> n >> k;
16
    for (int i = 1; i <= k; i++)
17
        cin >> a[i].l >> a[i].p >> a[i].s;
18
    sort(a + 1,a + k + 1);
19
    for (int i = 1; i <= k; i++)
20
    {
21
        deque<int>q;
22
        //单调队列里记录的是使dp[i - 1][k] - p[i] * k最大的k
23
        //上面的k不是题目里说的有k个人，是上文dp转移时枚举的k。不要搞混了
24

25
        q.push_back(max(a[i].s - a[i].l,0ll));
26
        //类似dp初始化，第一个k就是这个人能刷到的左端点
27
        for (int j = 1; j <= n; j++)
28
        {
29
            dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
30
            if (j >= a[i].l + a[i].s)
31
                continue;//如果j不在粉刷范围内
32
            while (!q.empty() && q.front() + a[i].l < j)
33
                q.pop_front();//排除不在粉刷范围内的k
34
            if (j < a[i].s)
35
            {
36
                int tmp = dp[i - 1][j] - j * a[i].p;//将dp[i - 1][j] - p[i] * j插入，这里的j就相当于上面注释里的k
37
                while (!q.empty() && dp[i - 1][q.back()] - q.back() * a[i].p < tmp)
38
                    q.pop_back();
39
                q.push_back(j);
40
            }
41
            else
42
                dp[i][j] = max(dp[i][j],dp[i - 1][q.front()] + a[i].p * (j - q.front()));//进行转移
43
        }
44
    }
45
    cout << dp[k][n];
46
    return 0;
47
}

Thanks for reading!

日记

周三 12月 11 2024

1553 字 · 9 分钟

life 日记