比赛入口

C

很简单，建图找一下最远点即可。
不过因为点值比较离散，所以用map存邻接表(cf传统艺能卡ump，所以还是不用的好)。
code:

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
void dfs(map<ll, vector<ll>>& nxt, map<ll, bool>& vs, ll p, ll &ans)
{
    vs[p] = true;
    ans = max(ans, p);
    for (auto s : nxt[p]) {
        if (!vs[s] && s != 0) {
            dfs(nxt, vs, s,ans);
        }
    }
}


void solve()
{
    int n;
    cin >> n;
    vector<ll>a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    map<ll, vector<ll>>nxt;
    for (int i = 1; i <= n; i++) {
        nxt[a[i] + i -1].push_back(a[i] + i * 2 - 2);
    }
    map<ll,bool>vs;
    ll ans = 0;
    dfs(nxt, vs, n, ans);
    cout << ans << endl;
    return;

}

D

D1需要求解最少cost,D2还要求解最少cost的方案数。

D1部分

首先分析题意，可以发现这是一个类似完全背包的问题。 所以我们可以背包dp解决。
设定状态\(dp[i]\)为取完\(a_1 ... a_i\)的最小费用。显然\(dp\)数组是单调非降的。对于每个下标\(r\),设\(l\)是满足\(\sum_{k=l}^{r} a[k] \leq b[i]\)的最小值，那么从\(l-1\)转移到\(r\)一定是最优的。于是有状态转移方程：
\[dp[r] = \min(dp[r],dp[l-1] + m-i)\]
于是问题转移到如何对于每一个\(r\)，在可以容忍的时间限下求出\(l\)。
对此，我们可以使用双指针。想象一个队列,队尾为\(l\)，待加入元素为\(a[r]\)
1. 当剩余容积\(rem\)大于等于物品\(a[r]\)的cost时，加入\(a[r]\),此时的\(\{l,r\}\)即为一组合法的转移参数，于是执行转移。
2. 当剩余容积\(rem\)小于物品\(a[r]\)的cost时，我们弹出队尾元素，更新剩余容积。
3. 特殊情况，当队列为空，且剩余容积\(rem\)小于物品\(a[r]\)的cost时，我们跳过这个物品。(操作即为l++,r++)
这样，我们便可以\(O(mn)\)求得答案。
可以预处理出所有的\({l,r}\)(官方题解),不过我就边求边dp了。
code(D1 dp部分):

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
vector<ll>dp(n + 1, inf);
dp[0] = 0;
for (int i = 1; i <= m; i++) {
    int l = 1, r = 1;
    int rem = b[i];
    for (; r <= n; ) {
        if (rem >= a[r]) {
            rem -= a[r];
            dp[r] = min(dp[r], dp[l - 1] + m - i);
            r++;
        }
        else {
            if (l == r) {
                l++;
                r++;
            }
            else {
                rem += a[l];
                l++;
            }
        }
    }
}
if (dp[n] == inf) {
    cout << -1 << endl;
}
else {
    cout << dp[n] << endl;
}

D2部分

在求解D1的过程中，我们选取的是一定最优的\(\{l,r\}\)对进行转移,但实际上同等优的可以有很多对，而我们想要计数最优方案的话，就要转移所有同等优的(计数所有同等优的)才行。
那么这实际上是一个从左区间到右点的转移，其他题解有用线段树进行区间转移优化的，不过实际上不需要，用双指针仍能做到，而且时间复杂度更优。
前面所说"同等优的转移"很模糊，实际上，"同等优"的左区间即为\(dp\)值相同的区间，那么最优区间是和\(dp[l]\)值相同的区间，这个区间的内的任何点转移到\(r\)的值是一样的，所以我们可以把这个区间的转移变成一次转移，对计数的贡献则是最优区间内所有方案数相加。(想想这是为什么)
设取完\(1-i\)d的最优方案数(最优转移路径数)为\(path[i]\),最优区间右端点为\(lr - 1\)
有状态转移方程： \[dp[r] = \min(dp[r],dp[l-1] + m-i)\]
\[\begin{align*} path[r] = \left\{ \begin{array}{ll} \sum_{i = l}^{lr}path[i] & &dp[r] > dp[l-1]+m-i\\ path[r] +\sum_{i = l}^{lr}path[i] & &dp[r] = dp[l-1]+m-i\\ path[r] & &dp[r] < dp[l-1]+m-i\\ \end{array} \right. \end{align*}\]

所以，我们需要在D1的基础上，对于求出所有\(r\)的最优转移区间\(\{l,lr\}\),而这个也可以通过双指针做到(注意性质:当\(r\)增大时，\(lr\)同样是单调非降的！)。
具体实现先思考一下会更好，以下是D2部分代码
code: 

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
void solve()
{

    int n, m;
    cin >> n >> m;
    vector<int>a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    //a.push_back(inf);
    vector<ll>dp(n + 1, inf);
    vector<ll>pa(n + 1, 0);//path
    dp[0] = 0;
    pa[0] = 1;
    for (int i = 1; i <= m; i++) {
        int l = 1, r = 1, lr = 1;
        int rem = b[i];
        ll cnt = 0;
        for (; r <= n; ) {
            if (lr < l) {
                cout << "error" << endl;
            }
            if (rem >= a[r]) {
                rem -= a[r];
                while (dp[lr-1] == dp[l-1] && lr <= r) {//lr == r : r-1 -> r 
                    cnt = (cnt + pa[lr-1]) % mod;
                    lr++;
                }

                if (dp[l-1] + m - i < dp[r]) {
                    dp[r] = dp[l-1] + m - i;
                    pa[r] = cnt;
                }
                else if (dp[l-1] + m - i == dp[r]) {
                    pa[r] = (pa[r] + cnt) % mod;
                }
                r++;
            }
            else {
                if (l == r) {
                    l++;
                    lr++;
                    r++;
                }
                else {
                    rem += a[l];
                    cnt = (cnt + mod - pa[l - 1]) % mod;;
                    l++;
                    while (lr < l) {
                        cnt = (cnt + pa[lr - 1]) % mod;
                        lr++;
                    }
                }
            }
        }
    }
    if (dp[n] == inf) {
        cout << -1 << endl;
    }
    else {
        cout << dp[n] << " " << pa[n] << endl;
    }
    return;
}