luogu P1880 [NOI1995]石子合并_会飞的蟋蟀的博客-程序员秘密

技术标签: 动态规划  luogu  

题解

第一次遇到区间dp的问题,这种解构问题的方法还是比较新颖的。
既然是dp,我们还是想要把全部的状态以及选择表达出来,怎样表示是个问题。

大概思路是

//mst(dp,0) 初始化DP数组
for(int i=1;i<=n;i++)
{
    dp[i][i]=初始值
}
for(int len=2;len<=n;len++)  //区间长度
for(int i=1;i<=n;i++)        //枚举起点
{
    int j=i+len-1;           //区间终点
    if(j>n) break;           //越界结束
    for(int k=i;k<j;k++)     //枚举分割点,构造状态转移方程
    {
        dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
    }
}

ps: 这道题按这种思路是 O(n^3)的复杂度,还可以进一步优化。(平行四边形优化)


Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int n,m;
int cot[202],pre[202];
int f1[202][202],f2[202][202];
int d(int i,int j){
    return pre[j] - pre[i-1];
}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>cot[i];
        cot[i+n] = cot[i];
    }
    for(int i=1;i<=n+n;i++) pre[i] = pre[i-1]+cot[i];

    for(int len=1;len<n;len++){
        for(int i=1,j=i+len;i<n+n && j< n+n;i++,j=i+len){
   // 环成链 i要迭代到n后面
            f2[i][j] = 1e9;
            for(int k=i;k<j;k++){
                f1[i][j] = max(f1[i][j], f1[i][k]+f1[k+1][j]+d(i,j));
                f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+d(i,j));
            }
        }
    }

    int maxp,minp;
    maxp=0,minp=99999999;
    for(int i=1;i<=n;i++){
        maxp = max(maxp,f1[i][i+n-1]);  
        minp = min(minp,f2[i][i+n-1]);  
    }

    cout<<minp<<endl<<maxp<<endl;
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/smmyy022/article/details/81943575

智能推荐

第8周项目1-1实现复数类中的运算符重载_fxy流年无悔的博客-程序员秘密

编号及代码:/**Copyright(c)2015,烟台大学计算机与工程学院*All rights reserved;*文件名称:score.cpp*作者:范星月*完成日期:2015年4月24日*版本号:v1.0**问题描述:实现复数类的运算符重载*问题输入:无*问题输出:负数*/#include using namespace

C语言函数之可变参数原理:va_start、va_arg及va_end !!!!!!和printascii在kernel启动前的应用_c ++可变参数va_start_find_xiaohei的博客-程序员秘密

说到C语言函数可变参数,我们最先想到的可能就是printf、scanf、printk了。在Linux-2.6.24.7内核源码里,printk函数原型如下:asmlinkage int printk(const char *fmt, ...)     asmlinkage表示通过堆栈传递参数。gcc编译器在汇编过程中调用c语言函数时传

笔记本过热、电脑cpu过热、限制CPU运行功率上限,轻松设置解决过热_cpu功率限制怎么调_@时间旅行者@的博客-程序员秘密

笔记本更换固态后发烫,不想使用散热器,以下方法教你限制cpu运行功率上限,让CPU减负。1.打开控制面板-----&gt;电源选项----&gt;更改计划设置----&gt;更改高级电源设置在新弹出的窗口中找到《处理器电源管理》-&gt;《最大处理器状态》-&gt;点击数字设置对应的参数,具体操作如下图:...

httpclient 设置短连接_HTTP长连接与短连接_weixin_39626745的博客-程序员秘密

HTTP的长连接和短连接本质上是TCP长连接和短连接。HTTP属于应用层协议,在传输层使用TCP协议,在网络层使用IP协议。 IP协议主要解决网络路由和寻址问题,TCP协议主要解决如何在IP层之上可靠地传递数据包,使得网络上接收端收到发送端所发出的所有包,并且顺序与发送顺序一致。TCP协议是可靠的、面向连接的。在HTTP/1.0中默认使用短连接。也就是说,客户端和服务器每进行一次HTTP操作,就建...

JavaScript数组的一些常用方法_Yahmm的博客-程序员秘密

前言数组是一个复杂数据类型,我们在操作它的时候就不能再想基本数据类型一样操作了比如我们想改变一个数组 // 创建一个数组 var arr = [1, 2, 3] // 我们想把数组变成只有 1 和 2 arr = [1, 2]这样肯定是不合理,因为这样不是在改变之前的数组相当于心弄了一个数组给到 arr 这个变量了相当于把 arr 里面存储的地址给换了,也就是把存储空间换掉了,而不是在之前的空间里面修改所以我们就需要借助一些方法,在不改变

随便推点

docker(二)——镜像_sober998的博客-程序员秘密

目录1:镜像的分层结构2:镜像的构建3:dockerfile的创建1:镜像的分层结构docker 镜像共享宿主机的kernel,base镜像提供的是最小的Linux发行版,同一docker主机支持运行多种Linux发行版。比如我们在宿主机上拉取一个busybox镜像,以交互式运行一个容器,执行uname -r命令,可以发现在容器中的操作系统和内核版本与宿主机相同。一个docker镜像由多个只读的镜像层组成,然后运行的容器会在这个docker的镜像上面多加一层可写的容器层,docker从上往下依次

Centos7 中docker开启远程访问_李昊轩的博客的博客-程序员秘密

首先,centos中docker的配置不同于ubuntu,在centos中没有/etc/default/docker,另外在centos7中也没有找到/etc/sysconfig/docke这个配置文件。参考了的farYang文章,配置好了centos7的docker远程访问,配置过程如下。在作为docker远程服务的centos7机器中配置:1、在/usr/lib/systemd/syst...

设置project甘特图任务间的前置重叠时间的方法_project前置任务的四种类型_swust_wjy的博客-程序员秘密

设置project甘特图任务间的前置重叠时间(任务相关性:两个链接任务之间的关系;通过完成日期和开始日期之间的相关性进行链接。有四种任务相关性类型:“完成-开始”(FS)、“开始-开始”(SS)、“完成-完成”(FF) 和“开始-完成”(SF)。)时,可能有一些后续任务 (后续任务:在另一个任务开始或完成之后才能开始或完成的任务。)可以在其前置任务 (前置任务:必须在另一个任务开始或完成之前开

如何在 Linux 上使用 Android Studio 设置 Flutter_linux 使用android st_mikes zhang的博客-程序员秘密

Flutter 是一个 Google 开发平台,可让您使用一个代码库编写跨平台移动应用程序。应用程序是用 Dart 开发的,Dart 是一种类型化和面向对象的语言,可以编译为本机代码或 JavaScript。这意味着您可以使用单个 Flutter 项目针对 Android、iOS、桌面操作系统和 Web。Flutter 附带了一个类似于 React 的框架,用于声明性地定义接口。它还附带内置 Material Design 和类似 iOS 的组件,可让您快速分层新界面。通过与 IDE、实时调试工具和测试.

ctfshow菜狗杯webwp_Msaerati的博客-程序员秘密

比如b=cookie[a],所以post[b]然后令post等于c所以get[c],令get=d所以request[d]最后补上前面的数字就是request[d],最后执行的就是eval(d[6][0][7][5][8][0][9][4][4]);可以看到源码对于输入的限制是两个正则,要求要么是数字,要么是dir(gmpy2)中的内容。根据源码可知,address是用AES的ECB模式加密的,稍微查一下就可以知道,ECB模式一组密文对应一组明文,也就是说,可以通过改变密文的顺序从而改变解密后明文的顺序。

QCC514X蓝牙音频片上系统引入自适应主动降噪技术_quickembed的博客-程序员秘密

虽然以 AirPods 为代表的无线耳机已经提供了相对舒适的佩戴感受,但其在嘈杂环境中的降噪体验仍不尽如人意,此外不是所有用户都喜欢那种纯粹的开放式、或完全与环境声隔绝的降噪效果。 好消息是,得益于高通为 QCC514X 蓝牙音频片上系统引入的“自适应主动降噪”技术,不久后的入耳式无线耳机或可带来媲美开放式耳机的智能降噪体验。  想要获得良好的降噪效果,最简单粗暴的方法,就是增强耳塞的密封性、其次是引入 ANC 算法,这也是许多用户从 AirPods 转投 AirPods Pro 的一个主要原因。

推荐文章

热门文章

相关标签