BZOJ 3675 [Apio2014]序列分割

2021-02-12 03:17

阅读：410

标签：pos cst main get else sum int return lint

题解：斜率优化，维护上凸包，类似右上半圆

滚动数组优化空间，DP时记录决策点

注意：注意sum[i]-sum[j]可能==0

出题人就给了32分QWQ

其实本代码有Bug但是数据没卡

对于直接把0元素去掉然后DP可能使得序列不足m

#include
#include
#include
using namespace std;
const int maxn=100009;
const int maxm=209;
typedef long long Lint;


int n,m;
Lint s[maxn];
int ref[maxn];

Lint f[maxn];
Lint g[maxn];

int p[maxn][maxm];

int q[maxn];
Lint Getk(int i){
	return g[i]-s[i]*s[i];
}

void putans(int x,int y){
	if(y==0)return;
	putans(p[x][y],y-1);
	printf("%d ",ref[x]);
}

int main(){
	scanf("%d%d",&n,&m);++m;
	int cnt=0;
	for(int i=1;i-s[i]*(s[q[h+1]]-s[q[h]])))++h;
//			printf("%d %d %d\n",j,i,q[h]);
			f[i]=g[q[h]]+(s[i]-s[q[h]])*s[q[h]];
			p[i][j]=q[h];
			while(h

BZOJ 3675 [Apio2014]序列分割

标签：pos cst main get else sum int return lint

原文地址：https://www.cnblogs.com/zzyer/p/8481033.html

上一篇：win7安装composer Failed to decode zlib stream

下一篇：arcgis api for js入门开发系列十七在线地图（天地图、百度地图、高德地图）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ 3675 [Apio2014]序列分割
文章链接：http://soscw.com/index.php/essay/54281.html

亲，登录后才可以留言！

BZOJ 3675 [Apio2014]序列分割

评论

热门文章

推荐文章

最新文章

置顶文章