【难题】动态规划 NOI 162:Post Office 7624:山区建小学——找状态方程有点难 思路详细

本文主要是介绍【难题】动态规划 NOI 162:Post Office 7624:山区建小学——找状态方程有点难 思路详细,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:点击打开链接

题目大意:V个村庄,P个邮局,邮局建在村庄上,求一种建法,让V个村庄到最近邮局的距离最小

dp[i][j]:表示在1~i个村庄中建j个邮局时的路径最小值 

m[i][j]:表示从i到j只建立一个邮局的路径的最小值

若从第i个村庄到第j个村庄只选取一个作为邮局的话则选择第(i+j)/2个

一开始我没懂,直到自己画了个图,假设把在5建的邮局移到4,则其他村庄的距离变化如图,从4到3不会变化,所以除法向下取整不会有问题。


则状态转移方程:m[i][j]=m[i][j-1]+a[i]-a[(i+j)/2]

怎么理解呢?
1)i+j为偶数,有以下序列,此时在2建邮局
    1 2 3
    新加一个村庄,此时还是在2建邮局
    1 2 3 4
    则m[1][4]=m[1][3]+(4到2的距离)a[4]-a[(1+4)/2]
2)i+j为奇数,有以下序列,此时在2建邮局
    1 2 3 4
    新加一个村庄,此时在3建邮局。根据之前画的图,村庄仅有1~4时,在2、3建邮局都是路径最小值,m[1][4]不会变化
    1 2 3 4 5
    则m[1][4]=m[1][3](邮局位置变了但是值不变)+(5到3的距离)a[5]-a[(1+5)/2]

所以得:
初始化:dp[i][1]=m[1][i]

dp[i][j]=min{dp[k][j-1]+m[k+1][i]}(1<=k<i)

思路参考了这位博主:点击打开链接

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int a[301],m[301][301]={0},dp[301][31]={0};
int main()
{int V,P,i,j,sum=0,k;cin>>V;cin>>P;for (i=1;i<=V;i++){cin>>a[i];sum+=a[i];}for (i=1;i<=V;i++)for (j=i+1;j<=V;j++)m[i][j]=m[i][j-1]+a[j]-a[(i+j)/2];//初始化dpfor (i=1;i<=V;i++)for (j=2;j<=P;j++)dp[i][j]=sum;for (i=1;i<=V;i++)dp[i][1]=m[1][i];//dpfor (i=1;i<=V;i++)for (j=2;j<=P;j++)for (k=j-1;k<i;k++)//因为1~k至少j-1个邮局,所以k>=j-1,k从j-1开始遍历dp[i][j]=min(dp[i][j],dp[k][j-1]+m[k+1][i]);cout<<dp[V][P];return 0;
}

7624:山区建小学 这道题思路类似,只需在输入时处理一下

a[i]为每一个山区的位置
mi[i][j],i到j之间建一个小学的路程

dp[i][j],1~i之间建了j个小学

注意:
1、不要忘记初始化:dp[i][1]=mi[1][i]
2、要保证状态转移方程中每一项都已算出来
     k>=j-1,k+1<=i,j-1>=1即j>=2

#include<iostream>
#include<string.h>
using namespace std;
int dp[501][501],a[501],mi[501][501];
int m,n;
int main()
{int i,j,x,k;cin>>m>>n;a[1]=0;for (i=2;i<=m;i++){cin>>x;a[i]=a[i-1]+x;}for (i=0;i<=m;i++)mi[i][i]=0;for (i=1;i<=m;i++)for (j=i+1;j<=m;j++)mi[i][j]=mi[i][j-1]+a[j]-a[(i+j)/2];for (i=1;i<=m;i++)for (j=1;j<=n;j++)dp[i][j]=250000;for (i=1;i<=m;i++)dp[i][1]=mi[1][i];for (i=2;i<=m;i++)for (j=2;j<=n;j++)for (k=j-1;k<i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+mi[k+1][i]);cout<<dp[m][n]<<endl;return 0;
}

这篇关于【难题】动态规划 NOI 162:Post Office 7624:山区建小学——找状态方程有点难 思路详细的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369563

相关文章

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

HTML img标签和超链接标签详细介绍

《HTMLimg标签和超链接标签详细介绍》:本文主要介绍了HTML中img标签的使用,包括src属性(指定图片路径)、相对/绝对路径区别、alt替代文本、title提示、宽高控制及边框设置等,详细内容请阅读本文,希望能对你有所帮助... 目录img 标签src 属性alt 属性title 属性width/h

CSS3打造的现代交互式登录界面详细实现过程

《CSS3打造的现代交互式登录界面详细实现过程》本文介绍CSS3和jQuery在登录界面设计中的应用,涵盖动画、选择器、自定义字体及盒模型技术,提升界面美观与交互性,同时优化性能和可访问性,感兴趣的朋... 目录1. css3用户登录界面设计概述1.1 用户界面设计的重要性1.2 CSS3的新特性与优势1.

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布局和层叠关

在Windows上使用qemu安装ubuntu24.04服务器的详细指南

《在Windows上使用qemu安装ubuntu24.04服务器的详细指南》本文介绍了在Windows上使用QEMU安装Ubuntu24.04的全流程:安装QEMU、准备ISO镜像、创建虚拟磁盘、配置... 目录1. 安装QEMU环境2. 准备Ubuntu 24.04镜像3. 启动QEMU安装Ubuntu4

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4

SQL Server数据库死锁处理超详细攻略

《SQLServer数据库死锁处理超详细攻略》SQLServer作为主流数据库管理系统,在高并发场景下可能面临死锁问题,影响系统性能和稳定性,这篇文章主要给大家介绍了关于SQLServer数据库死... 目录一、引言二、查询 Sqlserver 中造成死锁的 SPID三、用内置函数查询执行信息1. sp_w