首页 > 其他分享 >CF704B Ant Man

CF704B Ant Man

时间:2024-05-07 21:14:36浏览次数:23  
标签:std i64 min int max CF704B Ant 插入 Man

CF704B Ant Man

插入型 dp

分析排列的权值,如果排列确定,那么每个位置都有自己的贡献,并且无关其他位置的贡献。考虑 dp。从小到大将 \(p_i\) 插入序列中,此时序列会分成若干段,可设 \(f_{i,j}\) 插入了 \(1\cdots i\),序列分成 \(j\) 段的权值和。

转移通常有四种。

  1. 插入到一段的左边,此时 \(i\) 左右的大小情况确定,下面同理,于是可以转移 \(f_{i,j}=\max(f_{i,j},f_{i-1,j}+b_i+c_i)\)
  2. 插入到一段的右边,\(f_{i,j}=\max(f_{i,j},f_{i-1,j}+a_i+d_i)\)
  3. 将两段合并为一段,\(f_{i,j}=\max(f_{i,j},f_{i-1,j+1}+2\times x_{i}+a_{i}+c_{i})\)
  4. 建新的一段,\(f_{i,j}=\max(f_{i,j},f_{i-1,j-1}-2\times x_i+b_i+d_i)\)

考虑限制 \(s\) 和 \(e\),如果 \(i=s/e\),那么不需要转移所有。还有一些特殊情况,如果 \(i>\max(s,e)\) 并且此时 \(j=1\),那么无法合并;如果 \(i>s\) 且 \(j=1\),那么无法插入到左边;右边同理。

复杂度 \(O(n^2)\)。

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 10;
int n, s, e;
i64 x[N], a[N], b[N], c[N], d[N], f[N][N];
void Solve() {
	std::cin >> n >> s >> e;
	for(int i = 1; i <= n; i++) std::cin >> x[i];
	for(int i = 1; i <= n; i++) std::cin >> a[i];
	for(int i = 1; i <= n; i++) std::cin >> b[i];
	for(int i = 1; i <= n; i++) std::cin >> c[i];
	for(int i = 1; i <= n; i++) std::cin >> d[i];
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= i; j++) {
			if(i == s) {
				f[i][j] = std::min(f[i][j], f[i - 1][j] + x[i] + c[i]);
				f[i][j] = std::min(f[i][j], f[i - 1][j - 1] - x[i] + d[i]);
			} else if(i == e) {
				f[i][j] = std::min(f[i][j], f[i - 1][j] + x[i] + a[i]);
				f[i][j] = std::min(f[i][j], f[i - 1][j - 1] - x[i] + b[i]);
			} else {
				if(!(i > s && i > e && j <= 2)) f[i][j] = std::min(f[i][j], f[i - 1][j - 1] - 2 * x[i] + b[i] + d[i]);
				if(!(j == 1 && i > s)) f[i][j] = std::min(f[i][j], f[i - 1][j] + b[i] + c[i]);
				if(!(j == 1 && i > e)) f[i][j] = std::min(f[i][j], f[i - 1][j] + a[i] + d[i]);
				f[i][j] = std::min(f[i][j], f[i - 1][j + 1] + 2 * x[i] + a[i] + c[i]);  
			}
		}
	}
	std::cout << f[n][1] << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}

标签:std,i64,min,int,max,CF704B,Ant,插入,Man
From: https://www.cnblogs.com/FireRaku/p/18178386

相关文章

  • torch.manual_seed(seed)用法及注意事项
    torch.manual_seed(0)是PyTorch中的函数调用,用于设置随机数生成器的种子。通过指定种子值,我们可以确保每次运行代码时生成的随机数序列是相同的,这样有助于保持实验的可复现性。在深度学习中,训练过程中的随机化(例如权重初始化、数据采样等)可能会影响模型的性能和结果。因此,在进......
  • antd下拉选择框搜索配置:filterOption
     <SelectallowClearmode="multiple"showArrow={true}showSearch={true}filterOption={(inputValue,option)=>option?.props?.label.includes(inputVal......
  • jmeter插件管理器安装-Plugins Manager
    有些函数是jmeter自带函数,有些函数是自定义的需要通过插件安装的,例如jmeter没有自带base64加密函数,若要使用该函数,可以通过插件安装自定义函数1.下载jmeter插件管理器:https://jmeter-plugins.org/wiki/PluginsManager/ 2.重启在jmeter,在“选项”下显示插件管理器"Plugins......
  • C#获取计算机唯一标识组装GUID ,延伸ManagementClass、WIN32_类库名
    usingSystem.Management;usingSystem.Security.Cryptography;usingSystem.Text;namespaceSWin{publicclassComGUID{privatestaticstringcomputerGUID=string.Empty;publicstaticstringValue(){if(str......
  • uniapp开发小程序引入vant
    1.安装#通过npm安装npmi@vant/weapp-S--production#通过yarn安装yarnadd@vant/weapp--production#安装0.x版本npmivant-weapp-S--production2.引入项目首先在项目根目录创建文件夹wxcomponents,然后在其中创建vant文件夹。把node_modules......
  • 25 Prometheus和alertmanager高可用--Thanos
    一、prometheus高可用第一种方式1.准备3台centos服务器2.设置计算机名3.安装docker和docker-compose安装prometheus#2台安装prometheus服务mkdir/data/cd/data/gitclonehttps://gitee.com/linge365/docker-prometheus.gitcddocker-prometheusroot@os:/d......
  • WPF C# construct Grid,DataGrid,Button manually
    usingMicrosoft.Win32;usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;usingSystem.Windows;usingSystem.Windows.Controls;usingSystem.Windows.Data;usingSystem.Windows.Documents;usin......
  • openGauss CopyManager类简介
    CopyManager类简介CopyManager是openGaussJDBC驱动中提供的一个API接口类,用于批量向openGauss中导入数据。CopyManager的继承关系CopyManager类位于org.postgresql.copyPackage中,继承自java.lang.Object类,该类的声明如下:publicclassCopyManagerextendsObject构造方法......
  • 23 Alertmanager抑制、静默、路由、告警分组
    一、抑制机制Alertmanager的抑制机制可以避免当某种问题告警产生之后用户接收到大量由此问题导致的一系列的其它告警通知。例如当集群不可用时,用户可能只希望接收到一条告警,告诉他这时候集群出现了问题,而不是大量的如集群中的应用异常、中间件服务异常的告警通知。在Alertman......
  • JavaGUI - [03] LayoutManager布局管理器
    Component中有一个方法setBounds()可以设置当前容器的位置和大小,但如果我们手动为组件设置位置和大小的话,就会造成程序的不通用性。LayoutManager布局管理器可以根据运行平台来自动调整组件大小,程序员不用再手动设置组件的大小和位置,只需要为容器选择合适的布局管理器即可。 ......