题解 P2029 【跳舞】

皎月半洒花

2018-12-21 20:48:55

Solution

一道不是十分水的$dp$. 首先我们考虑$dp$方程的构造。起初我定义的状态是**$dp_{i,j}$表示前$i$个格子,总共跳了$j$次的最大得分**。但事实上它**并不可以转移**,因为我们不知道新的一轮操作从之间的哪个格子算起。 那么状态转移方程就出来了,我们把第一维改成**本次跳到第$i$个格子上,包括本次在内总共跳了$j$次的最大得分**,那么转移的时候,由于本次一定要跳到$i$上(如状态中所定义),所以不用分类讨论。方程就是:$$dp_{i,j}=\max\{dp_{k,j-1}-\rm{Sum(k + 1, i-1)}\}+A_i$$ 其中$0 \leq k < i(\text{不能两次跳到同一个格子上所以右区间为开区间})$,$\rm{Sum(l,r)}\mathcal{=\sum\limits_{i=l}^{r}A_i}$ 代码大概是这样$(\rm{30pts})$: ```cpp #include <cstdio> #include <iostream> #define MAXN 5010 using namespace std ; int i, j, k, Ans ; int N, T, S[MAXN], dp[MAXN][MAXN], A[MAXN], B[MAXN] ; int main(){ cin >> N >> T ; for (i = 1 ; i <= N ; ++ i) scanf("%d", &A[i]), S[i] = S[i - 1] + A[i] ; for (i = 1 ; i <= N ; ++ i) scanf("%d", &B[i]) ; for (i = 0 ; i <= N ; ++ i) for (j = 0 ; j <= N ; ++ j) dp[i][j] = -192608170 ; dp[0][0] = 0 ; for (i = 1 ; i <= N ; ++ i) for (j = 1 ; j <= i ; ++ j){ for (k = 0 ; k < i ; ++ k) dp[i][j] = max(dp[i][j], dp[k][j - 1] - S[i - 1] + S[k] + A[i]) ; if (j % T == 0) dp[i][j] += B[i] ; Ans = max(Ans, dp[i][j]) ; } cout << Ans << endl ; return 0 ; } ``` 但是我们发现,这个复杂度是$\Theta(n^3)$的,于是选择优化。$dp$优化的老套路就是: * 优化状态维数 * 优化转移复杂度 而此处我们不可以优化状态了,所以考虑优化转移复杂度。转移的复杂度是$\Theta(n)$的,我们考虑可否$\Theta(1)$转移,最终使得总复杂度为$\Theta(n^2) \times \Theta(1) \leq O(n^2)$ 从状态转移方程入手,我们发现有关于$k$是满足单调性的。所以不妨我们记录一下每次的$k$,即把$dp[k][j-1]+ S[k]$中的最大值存储下来,从而达到$\Theta(1)$转移的目的。 此处笔者使用了比较玄学的存储方式……类似刷表……当然这个地方有多种的优化方式啦~ 完整版$code$(700~800ms): ```cpp #include <cstdio> #include <iostream> #define MAXN 5010 using namespace std ; int i, j, k, p, Ans ; int N, T, Last[MAXN], S[MAXN], dp[MAXN][MAXN], A[MAXN], B[MAXN] ; int main(){ cin >> N >> T ; for (i = 1 ; i <= N ; ++ i) scanf("%d", &A[i]), S[i] = S[i - 1] + A[i] ; for (i = 1 ; i <= N ; ++ i) scanf("%d", &B[i]) ; for (i = 0 ; i <= N ; ++ i) for (j = 0 ; j <= N ; ++ j) dp[i][j] = -192608170 ; dp[0][0] = 0 ; for (j = 1 ; j <= N ; ++ j){ for (i = j ; i <= N ; ++ i){ p = Last[i - j], Last[i - j] = 0 ; dp[i][j] = p - S[i - 1] + A[i] ; if (j % T == 0) dp[i][j] += B[i] ; Ans = max(Ans, dp[i][j]) ; Last[i - j] = max(Last[i - j - 1], dp[i][j] + S[i]) ; } } cout << Ans << endl ; return 0 ; } ``` ~~毒瘤常数优化后被艹到龟速的版本~~(1100ms +): ```cpp #include <cstdio> #include <cstring> #include <iostream> #define max Max #define MAXN 5010 #define Inf 19260817 using namespace std ; int i, j, k, p, t, Ans ; int N, T, Last[MAXN], S[MAXN], dp[MAXN][MAXN], A[MAXN], B[MAXN] ; inline int Max(int a, int b){ return a & ((b - a) >> 31) | b & ( ~ (b - a) >> 31) ; } inline int qr(){ int res = 0 ; char c = getchar() ; while (!isdigit(c)) c = getchar() ; while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ; return res ; } int main(){ cin >> N >> T ; for (i = 0 ; i <= N ; ++ i) for (j = 0 ; j <= N ; ++ j) dp[i][j] = -Inf ; dp[0][0] = 0 ; for (i = 1 ; i <= N ; ++ i) A[i] = qr(), S[i] = S[i - 1] + A[i] ; for (i = 1 ; i <= N ; ++ i) B[i] = qr() ; for (j = 1 ; j <= N ; ++ j){ for (i = j ; i <= N ; ++ i){ t = i - j, p = Last[t], dp[i][j] = p - S[i - 1] + A[i] ; if (!(j % T)) dp[i][j] += B[i] ; Ans = max(Ans, dp[i][j]), Last[t] = max(Last[t - 1], dp[i][j] + S[i]) ; } } cout << Ans << endl ; return 0 ; } ``` 唉,先有常数后有天,反向优化$Sun$神仙啊