题解：AT_abc267_d - Index × A(Not Continuous ver.)

· · 题解

题意

给定一个长度为 n 的整数序列 a=(a_1,a_2,\dots,a_n) 。

求长度为 m 的 a 的子序列 b=(b_1,b_2,\dots,b_m) 的最大值 \displaystyle\sum_{i=1}^{M}i\times b_i（不一定连续）（以下称序列的“权值”）。

思路

一眼 DP。先观察条件：

  1. 序列长度；
  2. 已选元素个数；
  3. 序列的权值。

设计状态

显然，No.3 是我们要求的东西，而 No.1、No.2 缺一不可，且已知 No.1 和 No.2 就很容易推出 No.3，所以状态可以这样设计：f(i,j) 表示 a 中前 i 个元素中选了 j 个的最大权值，且第 i 个必须选。

状态转移

比较显然（由题易知）。

  // 状态转移
    memset(f, -0x3f, sizeof(f));
    for(int i = 1; i <= n; ++i) {
        f[i][1] = a[i]; // 初始状态
        for(int j = 1; j < i; ++j)
            for(int k = 1; k <= j && k < m; ++k)
                if(f[j][k] != -0x3f3f3f3f3f3f3f3f)
                    f[i][k + 1] = max(f[i][k + 1], f[j][k] + a[i] * (k + 1));
    }

注意到循环 k 时，for 的结束条件为 k <= j && k < m。其中 k < m 表示子序列长度不能超过 m；而 k <= j 是优化（很重要） ，表示已选元素不能超过 j。违反上述任意一条的状态都是无效的。

这样可以带来约 \dfrac{1}{8} 的优化。有什么用呢？有大用。你可以试着删掉优化，然后就会喜提 TLE。

分析一下时间复杂度，易知为 \mathrm{O}(n^2m)，其中 m\le n\le 2000，那么 n^2m\le 8\times 10^9。如不优化，会超时；若优化，即乘 \dfrac{1}{8}，则计算量最多为 10^9，再加上读入读出、高效缓存等各种常数（约 \dfrac{1}{4}），以及 AtCoder 强大的评测机，2 sec 以内可以通过。

答案状态

  // 答案状态
    long long ans = -0x3f3f3f3f3f3f3f3f;
    for(int i = 1; i <= n; ++i)
        ans = max(ans, f[i][m]);
    cout << ans << endl;

为什么不是 f(n,m) 呢？因为我们定义状态时规定了此时第 n 个元素必须选，然而这不一定是最优解，所以只能如代码那样。

完整代码

link

时间有点极限

总结

Update