日记 - 伊埃斯的博客站

上午

切了一题

CF2027D1 The Endspeaker (Easy Version)

还是那句话：~~既然出现在dp专题里，那肯定就是dp咯~~
我们设 $dp_{k,i,j}$ 表示在 $a_k = b_{i,j}$ 时能否获胜。我们发现，正着推好像不大行，那么，正难则反。
我们考虑从 $l \rightarrow 1,(i,j) \rightarrow (1,1)$ ，反着推。那么有明显的转移： $dp_{k,i,j} = \left[\left(\sum\limits_{x = i + 1}^{n}\sum\limits_{y = j + 1}^{m}dp_{k + 1,x,y}\right) = 0\right]$ 。但是，枚举状态就有 $\mathcal{O}(knm)$ 的复杂度了，转移还有 $\mathcal{O}(nm)$ 。合起来就是 $\mathcal{O}(kn^2m^2)$ 。这不给你T飞起来。
我们考虑怎么 $\mathcal{O}(1)$ 转移。我们发现， $\left(\sum\limits_{x = i + 1}^{n}\sum\limits_{y = j + 1}^{m}dp_{k + 1,x,y}\right)$ 可以用二维后缀和维护。那么最外面的循环枚举 $k$ （本该如此），然后里面是 $\mathcal{O}(nm)$ 的转移，等它转移完了，我们再 $\mathcal{O}(nm)$ 维护一下二维后缀和，这样就达到的 $\mathcal{O}(1)$ 转移的效果，总复杂度 $\mathcal{O}(knm)$ ，就可以了。

中午 & 下午

打了一下午游戏，在打游戏的时候尝试切一道线段树，但是失败了。

晚上

今天晚上又有 arc 又有 codeforces 的，本来都不想来，但是还是来学校打了。顺便把之前没写完的日记补了。

CF2027D The Endspeaker solution

我们先来看 easy version 。这一看就很有dp的感觉啊，于是我们就设 $dp_{i,j}$ 表示当 $k = i$ ，剩的第一个元素下标为 $j$ 的时候的最小代价。初始化时 $dp_{1,1} = 0$ 。然后我们就可以考虑如何转移：

第一种操作时，我们从 $j$ 开始找到第一个位置 $c$ 使得 $\sum\limits_{x = j}^{c} > b_i$ ，然后就可以转移： $dp_{i,c} = \min(dp_{i,c},dp_{i,j} + m - i)$ 。
第二种操作时，有显然的转移： $dp_{i + 1,j} = \min(dp_{i + 1,j},dp_{i,j})$ 。

然后怎么统计答案呢？我们想：要把 $a$ 数组去完，那么答案肯定是某个 $dp_{x,n + 1}$ （ $x$ 我们还不知道），然后，我们又发现，其实这个 $x$ 是多少无关紧要，那么我们就有答案： $ans = \min\limits_{i = 1}^{m}dp_{i,n + 1}$ 。

这是 easy version 啊，现在我们来看 easy version 的 hard version （ yzp 名言）
我们看 hard version 它 hard 在哪里。我们看：它不仅让我们求最小的代价是多少，他还让我们求有多少种方案能够达到最小的代价。我们发现，对于 $\forall p \in (j + 1,c]$ ，都可以从 $dp_{i,j}$ 转移： $dp_{i,p} = \min(dp_{i,p},dp_{i,j} + m - i)$ 。在简单版中不这么做是因为答案不会更优还浪费时间复杂度，而现在要统计方案数了，那么就要考虑一下了。而我们看要更新 $(j + 1,c]$ 这个区间，那么我们就想到线段树。
因为实现实在是太美所以就放一下代码：

1
#include<bits/extc++.h>
2
#define int long long
3
#define inf 0x7f7f7f7f7f7f7f7f
4
#define pii pair<int,int>
5
#define mkp make_pair
6
using namespace std;
7
const int maxn = 3e5 + 5;
8
const int mod = 1e9 + 7;
9
void operator+=(pii &x,pii &y)//这里就类似统计答案
10
{
11
    if(x.first != y.first)//如果方案更优就更新方案
12
    {
13
        if(x.first > y.first)
14
            x = y;
15
    }//这里一定一定要打大括号
16
    else//如果方案相同就更新方案数
17
        x.second = (x.second + y.second) % mod;
18
}
19
int n,m;
20
int a[maxn],b[maxn];
21
int pre[maxn];
22
struct Rukkhadevata//又好用码量又大的树：大慈树
23
{
24
    int l,r;
25
    pii val;
26
}tree[maxn << 2];
27
void push_down(int rt)
28
{
29
    if (tree[rt].val.first == inf)
30
        return;
31
    tree[rt << 1].val += tree[rt].val;
32
    tree[rt << 1 | 1].val += tree[rt].val;
33
    tree[rt].val = mkp(inf,0);
34
}//lazy下放
35
//为何直接拿val当lazy:因为不用维护区间查询，所以对于非叶子节点的val没有意义，就拿来当lazy
36
void build(int l,int r,int rt)
37
{
38
    tree[rt].l = l;
39
    tree[rt].r = r;
40
    tree[rt].val = mkp(inf,0);
41
    if (l == r)
42
    {
43
        if (l == 1)
44
            tree[rt].val = mkp(0,1);
45
        return;
46
    }
47
    int mid = l + r >> 1;
48
    build(l,mid,rt << 1);
49
    build(mid + 1,r,rt << 1 | 1);
50
}
51
void upd(int ql,int qr,pii x,int rt)
52
{
53
    int l = tree[rt].l;
54
    int r = tree[rt].r;
55
    if (ql <= l && r <= qr)
56
    {
57
        tree[rt].val += x;
58
        return;
59
    }
60
    push_down(rt);
61
    int mid = l + r >> 1;
62
    if (ql <= mid)
63
        upd(ql,qr,x,rt << 1);
64
    if (qr > mid)
65
        upd(ql,qr,x,rt << 1 | 1);
66
}
67
pii que(int x,int rt)
68
{
69
    int l = tree[rt].l;
70
    int r = tree[rt].r;
71
    if (l == r)
72
        return tree[rt].val;
73
    push_down(rt);
74
    int mid = l + r >> 1;
75
    if (x <= mid)
76
        return que(x,rt << 1);
77
    else
78
        return que(x,rt << 1 | 1);
79
}
80
void solve()
81
{
82
    scanf("%lld%lld",&n,&m);
83
    for (int i = 1; i <= n; i++)
84
    {
85
        scanf("%lld",a + i);
86
        pre[i] = pre[i - 1] + a[i];
87
    }
88
    for (int j = 1; j <= m; j++)
89
        scanf("%lld",b + j);
90
    build(1,n,1);
91
    pii ans = mkp(inf,0);
92
    for (int j = 1; j <= m; j++)
93
    {
94
        pii tmp1 = mkp(inf,0);
95
        for (int i = 1; i <= n; i++)
96
        {
97
            int pos = upper_bound(pre + i,pre + n + 1,b[j] + pre[i - 1]) - pre;//找到c
98
            if (i < pos)
99
            {
100
                pii tmp2 = que(i,1);
101
                tmp2.first += m - j;
102
                if (pos == n + 1)
103
                {
104
                    tmp1 += tmp2;
105
                    pos --;
106
                }
107
                if (i < pos)
108
                    upd(i + 1,pos,tmp2,1);//转移
109
            }
110
        }
111
        ans += tmp1;//记录答案
112
    }
113
    if (ans.first != inf)
114
        printf("%lld %lld\n",ans.first,ans.second);
115
    else
116
        puts("-1");
117
}
118
signed main()
119
{
120
    int t;
121
    scanf("%lld",&t);
122
    while (t--)
123
        solve();
124
    return 0;
125
}

Thanks for reading!

日记

周日 12月 08 2024

1226 字 · 8 分钟

life 日记