Atcoder-ABC369

水平有限，只做了ABCD。AB比较简单，这里只写了CD的题解。

C. 题目链接

算法标签：动态规划、数学。

思路：题目相当于求数组a中满足等差数列性质的子数组个数。使用动态规划求解，考虑dp[i]表示以 i 结尾的满足条件的子数组个数。状态转移 dp[i] = dp[i - 1] + 1，当且仅当 i ≥ 2 并且a[i] - a[i - 1] == a[i - 1] - a[i - 2]。最终结果 = sum(dp[i]) (0 ≤ i ≤ n-1)。

def solve():
    n = II()
    a = LII()
    dp = [1] * n
    tot = 1
    for i in range(1, n):
        dp[i] = 1
        if i >= 1:
            dp[i] += 1
        if i >= 2 and a[i] - a[i-1] == a[i-1] - a[i-2]:
            dp[i] = dp[i-1] + 1
        tot += dp[i]
    print(tot)

D. 题目链接

算法标签：动态规划。

思路：考虑每个位置选还是不选，如果选并且是第偶数个，那么价值要 * 2。状态转移 dp[i]  = max(不选，选 + a[i] * (2 if state == 1 else 1))，直接DFS加上记忆化就行了。

	static int n;
    static int[] a;
    static long[][] dp;

    static long dfs(int i, int state) {
        if (i >= n) return 0;
        if (dp[i][state] != -1) return dp[i][state];
        long x = dfs(i + 1, state);
        long y = 0;
        if (state == 1) {
            y = dfs(i +1 , state ^ 1) + 2L * a[i];
        } else {
            y = dfs(i + 1, state ^ 1) + a[i];
        }
        return dp[i][state] = Math.max(x, y);
    }

    public static void solve() throws IOException {
        n = in.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        dp = new long[n + 1][2];
        for (long[] d : dp) Arrays.fill(d, -1);

        long res = dfs(0, 0);
        out.println(res);
    }