网站哪个公司做的比较好,网站建设的设立方式,推广资源seo,wordpress 建站容易吗题目链接#xff1a;hdu 3507 Print Article 题意#xff1a; 每个字有一个值#xff0c;现在让你分成k段打印#xff0c;每段打印需要消耗的值用那个公式计算#xff0c;现在让你求最小值 题解#xff1a; 设dp[i]表示前i个字符需要消耗的最小值#xff0c;那么有dp[i]…题目链接hdu 3507 Print Article 题意 每个字有一个值现在让你分成k段打印每段打印需要消耗的值用那个公式计算现在让你求最小值 题解 设dp[i]表示前i个字符需要消耗的最小值那么有dp[i]min{dp[k](sum[i]-sum[k])2m)}(ki)。 这样是n2 的做法。 考虑用斜率优化 设kj,对于dp[i]从k1到i为一段比j1到i为一段更优。 那么有 dp[j](sum[i]-sum[j])2mdp[k](sum[i]-sum[k])2m 整理得 dp[j]sum[j]*sum[j]-(dp[k]sum[k]*sum[k])/sum[j]-sum[k]2*sum[i]。 不等式的右边就是一个斜率然后用单调队列优化做到O(n)的复杂度。 1 #includebits/stdc.h2 #define F(i,a,b) for(int ia;ib;i)3 using namespace std;4 5 const int N5e67;6 int n,m,dp[N],sum[N],Q[N],head,tail;7 8 int getx(int j,int k){return sum[j]-sum[k];}9 int gety(int j,int k){return dp[j]sum[j]*sum[j]-dp[k]-sum[k]*sum[k];}
10 int check(int i,int j,int k){return gety(i,j)*getx(j,k)gety(j,k)*getx(i,j);}
11
12 int main()
13 {
14 while(~scanf(%d%d,n,m))
15 {
16 F(i,1,n)scanf(%d,sumi),sum[i]sum[i-1];
17 head1,tail0;
18 Q[tail]0;
19 F(i,1,n)
20 {
21 while(headtailgety(Q[head1],Q[head])2*sum[i]*getx(Q[head1],Q[head]))head;
22 dp[i]dp[Q[head]](sum[i]-sum[Q[head]])*(sum[i]-sum[Q[head]])m;
23 while(headtailcheck(i,Q[tail],Q[tail-1]))tail--;
24 Q[tail]i;
25 }
26 printf(%d\n,dp[n]);
27 }
28 return 0;
29 } View Code 转载于:https://www.cnblogs.com/bin-gege/p/6150146.html
