fdssd
2024-10-08 10:06:11
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define MAXN 1005 using namespace std; unsigned long long f[MAXN][MAXN],w[MAXN]; int num[MAXN]; #define FZ(i,p)(f[i-1][p]+num[p+1]*num[p+1]) int i,p; int que[MAXN],tail,head; int n,m,j; bool turnup(int i,int p1,int p2,int p3) //p1>p2>p3 { unsigned long long y1=FZ(i,p1),x1=num[p1],y2=FZ(i,p2), x2=num[p2], y3=FZ(i,p3), x3=num[p3]; if((x2-x3)*(y1-y2)>(x1-x2)*(y2-y3))return 1; else return 0; }int ii,nn; int main() { scanf("%d",&nn); for(ii=1;ii<=nn;ii++) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&num[i]); } sort(num+1,num+n+1); for(i=1;i<=n;i++) f[0][i]=(num[i]-num[1])*(num[i]-num[1]); for(int i=1;i<=m;i++){ head=tail=1; que[tail++]=0; for(int j=1;j<=n;j++){ while(head<tail-1&&FZ(i,que[head+1])-FZ(i,que[head])<2*num[j]*(num[que[head+1]]-num[que[head]])) head++; int k=que[head]; f[i][j]=f[i-1][k]+(num[j]-num[k+1])*(num[j]-num[k+1]); while(head<tail-1&&turnup(i,j,que[tail-1],que[tail-2])==0) tail--; que[tail++]=j; } } printf("%I64d\n",f[m][n]); } }
最新文章
- webpack 使用优化指南
- oracle删除users表空间
- css居中解决方案
- 各种隐藏 WebShell、创建、删除畸形目录、特殊文件名、黑帽SEO作弊(转自核大大)
- SRM 595 DIV1 250
- IO流,File类的测试........课堂加总结
- i++问题
- 【转】C++的拷贝构造函数深度解读,值得一看
- python大数据工作流程
- 一大早居然有骗子还是傻子,真是莫名其妙的,QQ1913522040,一看就是刚申请不久的
- JavaScript——对this指针的新理解
- MySql数据库SQL语句将编码
- Node.js: What is the best "full stack web framework" (with scaffolding, MVC, ORM, etc.) based on Node.js / server-side JavaScript? - Quora
- 用js动态的改变img标签里面的src属性实现图片的循环切换
- HMC5883L地磁传感器驱动
- s3c2440 nandflash 初始化
- python 分享一个通过 (key1.key2.key3) 形式获取嵌套字典值的方法
- 计数器counter
- [Objective-C语言教程]字符串(16)
- NOIP 2018 记