首页 > 其他分享 >[AGC035D] Add and Remove

[AGC035D] Add and Remove

时间:2024-07-10 11:10:08浏览次数:14  
标签:插入 AGC035D Remove int Add 考虑

[AGC035D] Add and Remove

非常妙的一道题, 考虑最后剩下一定是 \(a[1]\) 和 \(a[n]\), 我们就想一想可不可以算每个数会对答案产生多少贡献?我们如果考虑加数似乎更方便? 考虑刚开始在 \(a[1]\) 和 \(a[n]\) 之间加入一个数 \(x\), 会产生 \(2 x\) 的贡献, 如果再在 \(x\) 和 \(a[n]\) 之间插入一个数 \(y\) 呢? 会产生 \(3y\) 的贡献! 这启发我们可以给每个数带一个系数, 枚举在两个数之间插入哪个数, 插入的数的系数就是两边的数的系数相加。

考虑这道题 \(n \leq 18\), 肯定乱搞随便过, 但我们还是证明一下, 考虑每个区间被遍历了一次, 所以时间复杂度 \(O(2^n)\)。

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20;
int a[N], n;
int dp(int l, int r, int xl, int xr) {
	if(r - l <= 1) return 0;
	int mn = 1e18;
	for(int k = l + 1; k < r; k++) 
		mn = min(mn, dp(l, k, xl, xl + xr) + dp(k, r, xl + xr, xr) + a[k] * (xl + xr));
	return mn;
}
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) 
		scanf("%lld", &a[i]);
	printf("%lld\n", dp(1, n, 1, 1) + a[1] + a[n]);
	return 0;
}

标签:插入,AGC035D,Remove,int,Add,考虑
From: https://www.cnblogs.com/qerrj/p/18293514

相关文章

  • / 用上指针 ,定义函数实现:终端输入 add + sub - mul * div / 执行 两个数 的加减乘除
    #include<stdio.h>#include<string.h>intmy_add(intdata1,intdata2){  returndata1+data2;}intmy_sub(intdata1,intdata2){  returndata1-data2;}intmy_mul(intdata1,intdata2){  returndata1*data2;}intmy_di......
  • Address Sanitizer
    AddressSanitizerIntroduction​ AddressSanitizer是一款内存检测器,它可以检测在堆栈,全局变量等地方的溢出。后来被整合到了GCC等编译器中,AddressSanitizer由两部分组成:一个Instrumentation模块和一个运行时库。Instrumentation模块修改代码来检查每个内存访问的影子状态,并......
  • CF292C Beautiful IP Addresses 题解(两种写法)
    题意一个IP地址是一个32位的2进制整数,分成四组8位的2进制整数(没有前导0)。比如说,0.255.1.123 是一个正确的IP地址,而0.256.1.123 和 0.255.1.01 不是正确的。定义一个合法的回文IP地址为BeautifulIPAddress(回文地址就是去掉“.”后是个回文字符串的地......
  • msaddsr.dll文件丢失导致程序无法运行问题
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个msaddsr.dll文件(挑选合适的版本文件)把它放......
  • 文字识别技术升级:Airtest与PaddleOCR模型的协作小技巧
    此文章来源于项目官方公众号:“AirtestProject”版权声明:允许转载,但转载必须保留原链接;请勿用作商业或者非法用途一、前言在进行自动化测试的过程中,ocr文字识别一直是大家最想要实现以及最需要的能力,今天就来介绍一个由百度飞浆提供的一个免费的ocr识别库——PaddleOCR,以及探......
  • 【漏洞复现】用友时空-KSOA-SQL注入-linkadd
    免责声明此内容仅供技术交流与学习,请勿用于未经授权的场景。请遵循相关法律与道德规范。任何因使用本文所述技术而引发的法律责任,与本文作者及发布平台无关。如有内容争议或侵权,请及时私信我们!0x01产品简介用友时空KSOA是建立在SOA理念指导下研发的新一代产品,是根据流......
  • 微信SDK与Unity的Addressables发生引用冲突的解决办法
    当我使用Unity的Addressables和微信的minigame-SDK时,会发生一个CS0433的报错,如下图所示: 关于CS0433错误,微软的官方文档中是这么描述的: 因此,根据报错信息,我揣测是Unity的Compat与mscorlib发生了重复,所以将mscorlib.dll文件全部删除了,但是问题没有得到解决,后面在一个大佬的帮......
  • PaddleNLP UIE 实体关系抽取
    目录环境依赖配置SSH克隆代码训练定制代码结构数据标注准备语料库数据标注导出数据数据转换doccanoLabelStudio模型微调问题处理找不到'paddlenlp.trainer'找不到GPUprotobuf==3.20.2CUDA/cuDNN/paddlePaddleNLPUIE实体关系抽取PaddlePaddle用户可领取免费TeslaV100在线算......
  • Nginx(openresty) X-Forwarded-For $proxy_add_x_forwarded_for 多层代理 通过map分割
    1nginx配置#配置多层反向代理,配置如下proxy_passhttp://ip或者域名/;proxy_connect_timeout60;proxy_send_timeout60;proxy_read_timeout60;proxy_set_headerUpgrade$h......
  • 如何使用 Services.AddDistributedMemoryCache
    参考资料:https://www.cnblogs.com/RainFate/p/16920591.html AI生成:在.NETCore中,Services.AddDistributedMemoryCache()方法用于注册分布式内存缓存。这是一个内存中的缓存解决方案,适用于需要在多个服务器或服务之间共享缓存数据的分布式系统。如何使用AddDistributedMemory......