解题：APIO 2014 序列分割

2021-06-22 01:05

阅读：288

标签：设计 targe scanf text names scan 顺序 blank img

题面

拆开式子我们发现切割顺序不影响答案，所以可以设计出一个$dp[i][j]$表示到$i$为止切了$j$刀的最大收益之类的，然后做个前缀和就可以转移了。

$dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k]*(sum[i]-sum[k]) )$

第一维显然还可以滚掉，这样就有了一个$O(n^2k)$的做法因为跑不满如果再卡卡常大概可以得到50pts的好成绩

开始优化，假如现在在$i$而先不管切了几刀，有两个位置$j$和$k$满足$j

$dp[j]+sum[j]*(sum[i]-sum[j])

$dp[j]-sum[j]^2-(dp[k]-sum[k]^2)

$\frac{dp[j]-sum[j]^2-(dp[k]-sum[k]^2)}{(sum[k]-sum[j])}

— —斜率优化，而sum[i]又是单增的，所以每次直接取队头就完事了

注意：因为是非负序列，可能会出现斜率不存在的情况，记得判掉

 1 #include 2 #include 3 #include
 4 using namespace std;
 5 const int N=100005,K=205;
 6 int n,k,f,b,p,tra[K][N],que[N];
 7 long long sum[N],dp1[N],dp2[N];
 8 double Slope(int a,int b)
 9 {
10     if(sum[a]==sum[b]) return -1e9;
11     return 1.0*(sum[b]*sum[b]-dp1[b]-(sum[a]*sum[a]-dp1[a]))/(sum[b]-sum[a]);
12 }
13 int main()
14 {
15     scanf("%d%d",&n,&k);
16     for(int i=1;i)
17         scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
18     for(int i=1;i)
19     {
20         f=0,b=-1;
21         for(int j=1;j)
22         {
23             while(f1]);
24             p=que[f],dp2[j]=dp1[p]+(sum[j]-sum[p])*sum[p],tra[i][j]=p;
25             while(f1],que[b])>=Slope(que[b],j)) b--;
26             que[++b]=j;
27         }
28         swap(dp1,dp2);
29     }
30     printf("%lld\n",dp1[n]),p=tra[k--][n];
31     while(p) printf("%d ",p),p=tra[k--][p];
32     return 0;
33 }

View Code

解题：APIO 2014 序列分割

标签：设计 targe scanf text names scan 顺序 blank img

原文地址：https://www.cnblogs.com/ydnhaha/p/10222171.html

上一篇：C#可变参数params

下一篇：Windows系统优化

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：解题：APIO 2014 序列分割
文章链接：http://soscw.com/essay/97151.html

亲，登录后才可以留言！

解题：APIO 2014 序列分割

评论

热门文章

推荐文章

最新文章

置顶文章