BZOJ 3675 [Apio2014]序列分割
标签：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
评论