算法杂记 2023/02/16

标签：02 val 16 样例 add 2023 array subtract dp

算法杂记 2023/02/16
- D. Different Arrays 2000

今天分享的是 Codeforce 上的一道 2000 分的动态规划 + 计数题。目前的目标是从紫冲橙。

D. Different Arrays `2000`

题面翻译

给你一个有 $n$ 个元素的序列，你需要进行 $n-2$ 次操作。

对于第 $i$ 次操作，你可以选择让 $a_i-a_{i+1}$ 且 $a_{i+2}+a_{i+1}$ 或者可以选择让 $a_i+a_{i+1}$ 且 $a_{i+2}-a_{i+1}$

问最后能产生多少个不同的序列。

题目描述

You are given an array $ a $ consisting of $ n $ integers.

You have to perform the sequence of $ n-2 $ operations on this array:

during the first operation, you either add $ a_2 $ to $ a_1 $ and subtract $ a_2 $ from $ a_3 $ , or add $ a_2 $ to $ a_3 $ and subtract $ a_2 $ from $ a_1 $ ;

during the second operation, you either add $ a_3 $ to $ a_2 $ and subtract $ a_3 $ from $ a_4 $ , or add $ a_3 $ to $ a_4 $ and subtract $ a_3 $ from $ a_2 $ ;

...

during the last operation, you either add $ a_{n-1} $ to $ a_{n-2} $ and subtract $ a_{n-1} $ from $ a_n $ , or add $ a_{n-1} $ to $ a_n $ and subtract $ a_{n-1} $ from $ a_{n-2} $ .

So, during the $ i $ -th operation, you add the value of $ a_{i+1} $ to one of its neighbors, and subtract it from the other neighbor.

For example, if you have the array $ [1, 2, 3, 4, 5] $ , one of the possible sequences of operations is:

subtract $ 2 $ from $ a_3 $ and add it to $ a_1 $ , so the array becomes $ [3, 2, 1, 4, 5] $ ;

subtract $ 1 $ from $ a_2 $ and add it to $ a_4 $ , so the array becomes $ [3, 1, 1, 5, 5] $ ;

subtract $ 5 $ from $ a_3 $ and add it to $ a_5 $ , so the array becomes $ [3, 1, -4, 5, 10] $ .

So, the resulting array is $ [3, 1, -4, 5, 10] $ .

An array is reachable if it can be obtained by performing the aforementioned sequence of operations on $ a $ . You have to calculate the number of reachable arrays, and print it modulo $ 998244353 $ .

输入格式

The first line contains one integer $ n $ ( $ 3 \le n \le 300 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 300 $ ).

输出格式

Print one integer — the number of reachable arrays. Since the answer can be very large, print its remainder modulo $ 998244353 $ .

样例 #1

样例输入 #1
4
1 1 1 1
样例输出 #1
3
样例 #2

样例输入 #2
5
1 2 3 5 0
样例输出 #2
7

显然，这题是 dp 题，这种计数题肯定是 dp 的思路。

从题解出发，假设我们使用一个最简单的思路，假设我们当前操作到第 $i$ 个元素，我们操作完后前 $i$ 个元素就已经固定，第 $i + 2$ 个元素后的元素也不会被影响。那么假设 dp 数组为 $dp_{i, x, y}$，其中 $i$ 表示第 $i$ 次操作， $x$ 表示第 $i$ 个元素， $j$ 表示第 $i + 1$个元素。假设我们把第 $a_i$ 加到 $a_{i+1}$ 上则我们应该将状态转移到 $dp_{i+1, y, a_{i+1}+y}$，否则我们需要转移到 $dp_{i+1,y, a_{i+1} - y}$。

这样思路非常清晰，考虑到时间复杂度需要 $O(n^3 \times \max(A)^2)$，我们需要进行一步优化。

可以发现，$x$ 位可以省略。并且操作位 $i$ 可以压缩到 $2$ 维。假设 $i=0$ 表示当前状态， $i=1$ 表示被更新到状态。

那么现在 dp 方程变为： $dp_{i, x}$ 代表操作完第 $i$ 个元素后，$a_{i+1}$ 的值为 $x$ 的可能情况数。

假设我们枚举的 $val$ 是 $a_{i}$ 的可能情况，由于 $val \in [-N, N]$ 其中 $N$ 代表一个 base offset。所以我们需要让他加上 $N$ 来保证始终为正数。

假设我们考虑的是添加 $val$ 到 $a_{i+1}$ 处，所以原始的结果应该是：$a[i+1] + val$。但是考虑到偏置 $N$ 的存在：

\[dp[1][(a[i+1] + val + N] \mathrel{+}= dp[0][val + N] \]

假设我们考虑的是减去 $val$ 到 $a_{i+1}$ 处，所以原始的结果应该是：$a[i+1]+val$。但是考虑到偏置 $N$ 的存在：

\[dp[1][a[i+1] -val +N] \mathrel{+}= dp[0][val + N] \]

同时，我们需要注意的是，如果 $val == 0$ 实际上两次转移是相同的，这样会重复，我们需要特殊考虑下这种情况，当 $val=0$ 时，我们只需要转移一次。

最后统计下 $ans = \sum dp[0][*]$ 即为答案。算法的时间复杂度为：$O(n\times \max(A)^2)$。

#include <bits/stdc++.h>
using namespace std;
#define DEBUG 0

#define vt std::vector
using ll = long long;
const int mod = 998244353;
const int N = 1e5 + 5;

void add(ll &x, ll y){
    x += y;
    while (x >= mod) x -= mod;
    if (x < 0) x += mod;
}

ll dp[2][2 * N + 1];
void solve(){
    int n;
    std::cin >> n;
    vt<int> a(n);
    for (int i = 0; i < n; ++ i)
        std::cin >> a[i];
    
    // dp[i][j] := 操作第 i 个元素，a_{i+1} 最后是 j 的可能情况
    memset(dp, 0, sizeof(dp));
    dp[0][a[1] + N] = 1;
    for (int i = 1; i + 1 < n; ++ i){
        for (int j = -N; j <= N; ++ j){
            if (dp[0][j + N] == 0) continue; // 避免了越界
            add(dp[1][a[i + 1] + j + N], dp[0][j + N]);
            if (j != 0)
                add(dp[1][a[i + 1] - j + N], dp[0][j + N]);
        }
        swap(dp[0], dp[1]);
        memset(dp[1], 0, sizeof(dp[1]));
    }

    ll ans = 0;
    for (int i = 0; i < 2 * N; ++ i)
        add(ans, dp[0][i]);
    std::cout << ans << "\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}

最后这里有一个类似的题目 CF#808 Div2 D. Difference Array ，在整个题目描述上非常类似，可以之后也做一下。

标签：02,val,16,样例,add,2023,array,subtract,dp
From： https://www.cnblogs.com/Last--Whisper/p/17128656.html

算法杂记 2023/02/16