当前位置: 首页 > news >正文

南宁致峰网站建设建设部注册中心网站

南宁致峰网站建设,建设部注册中心网站,重庆网站制作福州,福利吧 wordpress主题传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 给你一个长度为nnn的序列aaa#xff0c;你需要将其分成若干组#xff0c;每组的价值为max⁡(ai)−min(ai)\max(a_i)-min(a_i)max(ai​)−min(ai​)#xff0c;求如何分组才能使得代价最小#xff0c;输出…传送门 文章目录题意思路题意 给你一个长度为nnn的序列aaa你需要将其分成若干组每组的价值为max⁡(ai)−min(ai)\max(a_i)-min(a_i)max(ai​)−min(ai​)求如何分组才能使得代价最小输出最小代价以及分组方案。 3≤n≤2e5,1≤ai≤1e93\le n\le2e5,1\le a_i\le1e93≤n≤2e5,1≤ai​≤1e9 思路 首先可以将这个数组排个序不过要在排序之前记录一下编号。 排序之后就可以大力dpdpdp了定义f[i]f[i]f[i]表示到了第iii个数的最小代价那么肯定是从[1,i−3][1,i-3][1,i−3]转移过来但是这样转移是n2n^2n2的需要优化一下。 通过多写几组可以发现我们如果分出来了个长度为666的组那么把它分成俩长度为333的组答案一定不会变劣。所以我们只需要从[i−6,i−3][i-6,i-3][i−6,i−3]转移过来那么转移方程就是f[ij]min(f[ij],f[i−1]a[ij].val−a[i].val)f[ij]min(f[ij],f[i-1]a[ij].val-a[i].val)f[ij]min(f[ij],f[i−1]a[ij].val−a[i].val) 输出方案的时候记录一下组数就好啦没有要求组数最少随便找一组即可。 // Problem: E. Yet Another Division Into Teams // Contest: Codeforces - Codeforces Round #598 (Div. 3) // URL: https://codeforces.com/contest/1256/problem/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math) //#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative) //#pragma GCC optimize(2) #includecstdio #includeiostream #includestring #includecstring #includemap #includecmath #includecctype #includevector #includeset #includequeue #includealgorithm #includesstream #includectime #includecstdlib #includerandom #includecassert #define X first #define Y second #define L (u1) #define R (u1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].ltr[u].r)1) #define Len(u) (tr[u].r-tr[u].l1) #define random(a,b) ((a)rand()%((b)-(a)1)) #define db puts(---) using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); } //void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); } //void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f; const double eps1e-6;int n; LL f[N]; int ans[N],tot; struct Node {int val,id;bool operator (const Node W) const {return valW.val;} }a[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf(%d,n);for(int i1;in;i) scanf(%d,a[i].val),a[i].idi;sort(a1,a1n);memset(f,INF,sizeof(f));f[0]0;for(int i1;in;i) {for(int j2;j5;j) f[ij]min(f[ij],f[i-1]a[ij].val-a[i].val);}for(int in;i1;) {for(int j3;j5;j) if(i-j0f[i]f[i-j]a[i].val-a[i-j1].val) {tot;for(int hi-j1;hi;h) ans[a[h].id]tot;i-j;break;}}coutf[n] totendl;for(int i1;in;i) printf(%d ,ans[i]); puts();return 0; } /**/
http://www.sadfv.cn/news/344742/

相关文章:

  • 重庆制作网站培训百度推广关键词价格查询
  • 东莞外贸网站制作服装网站建设优点与缺点
  • 购物网站建设费用湖南省重点建设项目办公室网站
  • 阿里云服务器的网站备案学校门户网站建设的好处
  • 网站建设公司如何盈利做静态网站多少钱
  • 建立网站的连接结构有哪几种形式适合友情链接的网站
  • 网站多久会被百度收录郑州做网站推广电话
  • dedecms做网站怎么查看特色美食网站建设
  • 重庆网站建设的价格网站域名跳转
  • 做网站准备内容官方网站如何建设
  • 北京企业网站建设报价都达科技股份有限公司网页设计
  • 反钓鱼网站建设期wordpress分类目录高亮
  • 做玩网站怎么上传做军事网站的项目背景图片
  • 建站公司外包温州专业网站制作设计
  • 网站型建设模板互联网站账户e服务平台
  • 上海网站备案审核深圳推广软件十年乐云seo
  • 江苏省昆山市网站制作淘宝客如何做淘宝客网站推广
  • 把开发的网站让外网能访问要怎么做百度推广管家
  • 淄博网站建设推广乐达wordpress网易邮箱
  • 秦皇岛做网站公司国外服装购物网站大全
  • 做包装盒效果图的网站如何自己安装wordpress
  • 怎么看网站是否被k过设计素材网站会员
  • 电脑自带的做网站叫什么wordpress只导出设置
  • wordpress用什么空间怎样优化网站关键词
  • 台州手机网站开发网站 设计 案例 简单
  • 网站信息化建设领导小组好看的电商网站模板
  • 网站怎么做301定向网站开发实习总结
  • 网站服务内容有哪些临安网站开发
  • 做网站会遇到哪些问题涿州做网站的
  • 网站设计怎么学长沙网站建设外包