【SDUT [2146]最小子序列和】
发布日期:2021-11-04 12:59:32 浏览次数:12 分类:技术文章

本文共 1018 字,大约阅读时间需要 3 分钟。

最小子序列和

Time Limit: 1000MS Memory Limit: 65536KB
Problem Description

给你一个长为n(10<=n<=10000)的数组,数组中的每一个数大于等于1小于等于1000000。请你找出一个长为k(100<=k<=1000)的子序列。找序列时,假如第一个数找的是数组中的第i个位置的数,那么找第二个数时只能找数组中第i个位置后的数,依次找出k个数。使得第一个数*1+第二个数*2+…+第k个数*k的值最小。

Input

有多组(小于11组)测试数据,每组第一行输入n和k(用空格隔开),第二行输入n个数(数之间用空格隔开)。

Output

请输出最小的和。

Example Input

15 5

5 4 3 2 1 1 2 3 4 5 5 4 3 2 1
Example Output

19

#include
#include
using namespace std;int pa[100011];int dp[2][100011];int main(){ int i,n,k,pl,j,ans; while(scanf("%d%d",&n,&k)!=EOF) { for (i = 1 ;i <= n; i++) scanf("%d",&pa[i]); memset(dp,0,sizeof(dp)); for(i = 1; i <= k; i++) { ans = 0x3f3f3f3f; for( j = i ; j <= n ; j++) { dp[1][j] = dp[0][j-1] + pa[j] * i; //当前最优解 = 在 j 之前的最优解 + pa[j] * i; dp[0][j-1] = ans; // 当前 j-1最优解 if(ans > dp[1][j]) ans = dp[1][j]; } } printf("%d\n",ans); } return 0;}

转载地址:https://blog.csdn.net/WYK1823376647/article/details/52511331 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【zzulioj 1841 so easy!麻麻再也不用担心我的数学了!】
下一篇:【zzulioj 1837 LT说我不服 + dp】

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月17日 18时10分11秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了... 2019-04-21
linux 8086下编译,Ubuntu18.04/Linux下安装DosBox进行8086汇编 2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置 2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解 2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构 2019-04-21
mysql构建url给scrapy_Python Scrapy从mysq填充起始url 2019-04-21
owdcloud mysql_MySQL在Ubuntu远程配置 2019-04-21
python基础装饰器_Python基础 装饰器及练习 2019-04-21
python导出csv不带引号的句子_不带双引号写入CSV文件 2019-04-21
python爬虫代码模板_Python:学习Python爬虫的第一天 2019-04-21
springboot获取原生js请求_springboot跳转原生html 2019-04-21
java buffer nio_Java NIO之Buffer(缓冲区)入门 2019-04-21
android java加密_android 和java平台通用的AES加密解密 2019-04-21