Eous的小站
日记

日记

Wed Dec 11 2024
9 分钟
life 日记
1573 字

上午#

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

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

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

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

这是选了一个的状态

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

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

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

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

UVA12983 The Battle of Chibi#

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

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

下午#

P10978 Fence#

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

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

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

CPP
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
#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
int n,k;
int dp[105][16005];
struct Nahida{int l,p,s;}a[105];
bool operator<(const Nahida &x,const Nahida &y){return x.s < y.s;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
        cin >> a[i].l >> a[i].p >> a[i].s;
    sort(a + 1,a + k + 1);
    for (int i = 1; i <= k; i++)
    {   
        deque<int>q;
        //单调队列里记录的是使dp[i - 1][k] - p[i] * k最大的k
        //上面的k不是题目里说的有k个人，是上文dp转移时枚举的k。不要搞混了

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