[ABC267D] Index × A(Not Continuous ver.) Solution

更好的阅读体验戳此进入

题面

求序列 $A_n$$A_n$ 的长度为 $m$$m$ 的最大权值子序列 $B_m$$B_m$，定义序列 $B_m$$B_m$ 的权值为 $\sum _{i=1}^{m}i\times B_i$$\sum_{i = 1}^m i \times B_i$。输出最大权值。

Solution

提供一种不同的思路。

一种显而易见的思路就是考虑 $i$$i$ 是否选，则 DP 是 $\mathtt{\text{2D0D}}$$\texttt{2D0D}$ 的，这里提供一种 $\mathtt{\text{2D1D}}\to \mathtt{\text{2D0D}}$$\texttt{2D1D} \rightarrow \texttt{2D0D}$ 的做法。

我们考虑一个类似 LIS 的做法，考虑令 $dp(i,j)$$dp(i, j)$ 表示长度为 $i$$i$ 的以 $j$$j$ 结尾的子序列的最大权值，转移显然为：

即考虑从之前的某一个最优子序列拼过来。

这个东西十分显然可以简单写一个前缀和优化，最终复杂度 $O(n^2)$$O(n^2)$。

初始值即为 $dp(0,i)=0$$dp(0, i) = 0$，注意初始时需要将除了 $0$$0$ 之外的所有 $sum$$sum$ 都初始化为 $-\mathrm{\infty }$$-\infty$，否则因为负权值可能存在一些不正确的转移。

Code

xxxxxxxxxx
58
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M;
26
ll A[2100];
27
ll dp[2100][2100];
28
ll sum_mx[2100][2100];
29

30
int main(){
31
    memset(sum_mx, 0xc0, sizeof sum_mx);
32
    N = read(), M = read();
33
    for(int i = 0; i <= N; ++i)sum_mx[0][i] = 0;
34
    for(int i = 1; i <= N; ++i)A[i] = read();
35
    for(int i = 1; i <= M; ++i)
36
        for(int j = 1; j <= N; ++j)
37
            dp[i][j] = sum_mx[i - 1][j - 1] + A[j] * i,
38
            sum_mx[i][j] = max(sum_mx[i][j - 1], dp[i][j]);
39
    printf("%lld\n", sum_mx[M][N]);
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43

44
template < typename T >
45
inline T read(void){
46
    T ret(0);
47
    int flag(1);
48
    char c = getchar();
49
    while(c != '-' && !isdigit(c))c = getchar();
50
    if(c == '-')flag = -1, c = getchar();
51
    while(isdigit(c)){
52
        ret *= 10;
53
        ret += int(c - '0');
54
        c = getchar();
55
    }
56
    ret *= flag;
57
    return ret;
58
}

UPD

update-2023_01_14 初稿