526互联

codeforces 1783D Different Arrays

发布时间 2023-04-06 10:53:44作者: 冯文健

https://codeforces.com/contest/1783/problem/D

解题思路

比较直白的动态规划问题。记 f[i][j] 表示前 i 个元素组成以 j 结尾的序列可能的数量。那么，当第 i+1 个元素加入序列的时候有两种选择：加上第 i 个元素；减去第 i 个元素。

于是可以得到转移方程 f[i+1][a[i+1] - j] += f[i][j]；f[i+1][a[i+1] + j] += f[i][j]。注意，当 j == 0时，加减是等效的只能算一次。转移方程第二维会出现负数，用数组模拟的时候注意处理下标偏移不要越界。

/* https://codeforces.com/problemset/problem/1783/D */
#include <bits/stdc++.h>
using namespace std;

#define M 998244353
int dp[301][180001], n, a[301];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    while (cin >> n) {
        int max = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (max < a[i]) {
                max = a[i];
            }
        }
        max *= n;
        
        memset(dp, 0, sizeof(dp));
        dp[3][a[3]-a[2]+90000] = 1;
        dp[3][a[3]+a[2]+90000] = 1;
        for (int i = 4; i <= n; i++) {
            for (int j = -max; j <= max; j++) {
                int idx = j + 90000;
                if (dp[i-1][idx] == 0) {
                    continue;
                }
                int tmp = a[i] - j + 90000;
                dp[i][tmp] = (dp[i][tmp] + dp[i-1][idx]) % M;
                if (j != 0) {
                    tmp = a[i] + j + 90000;
                    dp[i][tmp] = (dp[i][tmp] + dp[i-1][idx]) % M;
                }
            }
        }

        int ans = 0;
        for (int j = -max; j <= max; j++) {
            if (dp[n][j+90000] == 0) {
                continue;
            }
            ans = (ans + dp[n][j+90000]) % M;
        }
        cout << ans << endl;
    }

    return 0;
}