$Luogu P2029$ 跳舞 题解

时间：2021-11-01 05:37:49

一道不是十分水的\(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})\)：

#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）:

#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 +）：

#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\)神仙啊

随机推荐

  1. CentOS 安装Paramiko模块

    转自:http://www.cnblogs.com/hyli/p/3910585.html 1.下载安装包: https://pypi.python.org/packages/source/p/par ...

  2. html meta标签使用总结

    meta标签作用 META标签是HTML标记HEAD区的一个关键标签,提供文档字符集.使用语言.作者等基本信息,以及对关键词和网页等级的设定等,最大的作用是能够做搜索引擎优化(SEO). PS:便于搜 ...

  3. git分支管理策略

    http://www.ruanyifeng.com/blog/2012/07/git.html https://www.digitalocean.com/community/tutorials/how ...

  4. angularJS图表-angular-flot

    1.首先需要在项目中引入的js文件有 <script src="http://cdnjs.cloudflare.com/ajax/libs/jquery/2.1.1/jquery.mi ...

  5. javascript OOP编辑思想的一个实践参考

    <html> <style type="text/css"> .current { background-color: red; } .dv { backg ...

  6. 写了一个迷你confirm弹窗插件，有取消和确认操作处理并支持单个确认使用弹窗和锁屏禁止滚动

    由于项目想精简不想用其他第三方的ui插件,又很需要像confirm等小效果来完善交互,且使用的频率也是相当的高,于是自己造了一个,省时也省力 代码已经粘贴出来,直接复制即可看到效果,高手勿喷,可以相互 ...

  7. 简单理解epel源

    EPEL源-是什么全称   EPEL源   EPEL (Extra Packages for Enterprise Linux)是基于Fedora的一个项目,为“红帽系”的操作系统提供额外的软件包,适 ...

  8. query

  9. 清除浏览器CSS样式

    /* YUI 3.18.1 (build f7e7bcb) Copyright 2014 Yahoo! Inc. All rights reserved. Licensed under the BSD ...

  10. Centos7 Nginx 开机启动

    Centos 系统服务脚本目录: 用户(user) 用户登录后才能运行的程序,存在用户(user) /usr/lib/systemd/ 系统(system) 如需要开机没有登陆情况下就能运行的程序,存 ...

相关文章