題目大意：將n個數分成若干組，并且每組的數在原數組中應是連續的，每組會產生的代價為sum(i)-sum(j)+i-j-1-m，m為已知的常數。求最小代價。

題目分析：定義dp(i)表示將前 i 個元素分好組后產生的最小代價，狀態轉移方程很顯然了：

dp(i)=min(dp(j)+[sum(i)-sum(j)+i-j-1-m)]^2)。另f(i)=sum(i)+i，并且另g(i)=f(i)-1-m，則dp(i)可整理成dp(i)=min(dp(j)+sum(j)^2-2*g(i)*sum(j))+g(i)。很顯然需要斜率優化。

?

代碼如下：

# include<iostream> # include<cstdio> # include<cstring> # include<algorithm> using namespace std; # define LL long longconst int N=50005;int n,m; int q[N]; LL a[N]; LL dp[N]; LL sum[N];void read(LL &x) {char ch=' ';while(ch<'0'||ch>'9')ch=getchar();x=0;while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} }void init() {sum[0]=0;for(int i=1;i<=n;++i){read(a[i]);sum[i]=a[i]+sum[i-1];}for(int i=1;i<=n;++i)sum[i]+=i; }LL getSon(int k,int j) {return dp[j]-dp[k]+(sum[j]+sum[k])*(sum[j]-sum[k]); }LL getMother(int k,int j) {return 2*(sum[j]-sum[k]); }double getK(int i,int j) {return (double)getSon(i,j)/(double)getMother(i,j); }LL toDp(int j,int i) {return dp[j]+(sum[i]-sum[j]-m-1)*(sum[i]-sum[j]-m-1); }LL solve() {int head=0,tail=-1;q[++tail]=0;dp[0]=0;for(int i=1;i<=n;++i){while(head+1<=tail&&getK(q[head],q[head+1])<=sum[i]-m-1)++head;dp[i]=toDp(q[head],i);while(head+1<=tail&&getK(q[tail-1],q[tail])>getK(q[tail],i))--tail;q[++tail]=i;}return dp[n]; }int main() {while(~scanf("%d%d",&n,&m)){init();printf("%lld\n",solve());}return 0; }

　　

轉載于:https://www.cnblogs.com/20143605--pcx/p/5304427.html

總結

以上是生活随笔為你收集整理的BZOJ-1010 玩具装箱toy （斜率优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。