HDU 3507 - Print Article
题意：
一个长度为n的序列，你可以将其分成任意段，每段的花费为sum[i....j]2+M,求整个序列的最小花费
思路：
dp求解,f[i]表示前i项的最小代价,s为前缀和
转移方程f[i]=min(f[i],f[j]+(s[i]-s[j])^2+M),dp复杂度O(N^2),使用斜率优化。
设f[i]转移从j比k好(k < j < i) 得斜率方程
f[j]+(s[i]-s[j])^2 +M<f[k]+(s[i]-s[k])^2+M 约去相同项 jk项移至左测 i和常移至右侧得
((f[j] + s[j]^2) - (f[k] + s[k]^2))/(s[j]-s[k])<2s[i]
令y = f[j]+s[j]^2 ,x=s[j] 则可以表示为点(y, x)计算斜率 表示为
(yj-yk)/(xj-xk)<2s[i]为了精度改乘法(yj-yk) <2s[i]*(xj-xk) 注意符号
当斜率小于2s[i]时 可以直接淘汰j点
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=5e5+100; ll dp[maxn],sum[maxn],p[1000006]; ll pow(ll x){return x*x;} ll getx(int i,int j) { return dp[j]+pow(sum[j])-dp[i]-pow(sum[i]); } ll gety(int i,int j) { return 2*(sum[j]-sum[i]); } int main() { ll n,m; while(scanf("%lld%lld",&n,&m)!=EOF){ for(int i=1;i<=n;i++){ scanf("%lld",&sum[i]); sum[i]+=sum[i-1]; } int tail=0,head=0; p[tail++]=0; for(int i=1;i<=n;i++){ while(head+1<tail&&getx(p[head],p[head+1])<=sum[i]*gety(p[head],p[head+1])) head++; dp[i]=dp[p[head]]+pow(sum[i]-sum[p[head]])+m; while(head+1<tail&&gety(p[tail-2],p[tail-1])*getx(p[tail-1],i)<=gety(p[tail-1],i)*getx(p[tail-2],p[tail-1])) tail--; p[tail++]=i; } cout<<dp[n]<<endl; } }
HDU 2829 - Lawrence(斜率DP)
题意：
一个长度为n的序列，进行m次分割，分割之后每段的值为该段内任意两数乘积的和，求所有段值的和的最小值
思路：
假设dp[i][j]为前i个元素进行j次分割后的最小值，cost[i]表示从1~i的数两两相乘的总和，sum[i]表示前i个数的和
则：dp[i][j]=Min(dp[k][j-1]+cost[i]-cost[k]-sum[k]*(sum[i]-sum[k]))=>dp[i][j]=dp[k][j-1]+cost[i]-cost[k]-sum[i]*sum[k]+sum[k]*sum[k]
由于有sum[i]*sum[k]这一项,所以不可能用单调队列维护-cost[k]-sum[i]*sum[k]+sum[k]*sum[k]的最小值，所以我们要把sum[i]独立出来以便求维护单调队列是和i无关
现在我们需要找出最优的k,令k2<k时k时最优的,即前k个数k为最优的取值
所以满足：
dp[k][j-1]+cost[i]-cost[k]-sum[i]*sum[k]+sum[k]*sum[k]<=dp[k2][j-1]+cost[i]-cost[k2]-sum[i]*sum[k2]+sum[k2]*sum[k2]
=>(dp[k][j-1]-cost[k]+sum[k]*sum[k]-(dp[k2][j-1]-cost[k2]+sum[k2]*sum[k2]))/(sum[k]-sum[k2])<=sum[i]
设:y1=dp[k][j-1]-cost[k]+sum[k]*sum[k] x1=sum[k] ，y2=dp[k2][j-1]-cost[k2]+sum[k2]*sum[k2] x2=sum[k2]
所以变成:(y2-y1)/(x2-x1)，即两点之间的斜率! 之后就是经典的斜率DP问题啦，维护一个下凸包来存储最大值
#include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn=1005; ll dp[maxn][2],sum[maxn],q[10000],a[maxn],c[maxn]; ll n,m,index; ll pow(ll x){return x*x;} int GetY(int k,int k2){ return dp[k][index^1]-c[k]+sum[k]*sum[k]-(dp[k2][index^1]-c[k2]+sum[k2]*sum[k2]); } int GetX(int k,int k2){ return sum[k]-sum[k2]; } void DP() { index=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][index]=c[i]; for(int j=1;j<=m;j++){ index=index^1; int tail=0,head=0; q[tail++]=0; for(int i=1;i<=n;i++){ while(head+1<tail && GetY(q[head+1],q[head])<=GetX(q[head+1],q[head])*sum[i]) head++; dp[i][index]=dp[q[head]][index^1]+c[i]-c[q[head]]+sum[q[head]]*(-sum[i]+sum[q[head]]); while(head+1<tail && GetY(i,q[tail-1])*GetX(q[tail-1],q[tail-2])<=GetY(q[tail-1],q[tail-2])*GetX(i,q[tail-1])) tail--; q[tail++]=i; } } } int main() { while(scanf("%lld%lld",&n,&m)&&n&&m){ for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) c[j]+=a[j]*a[i]; for(int i=1;i<=n;i++) c[i]+=c[i-1]; DP(); cout<<dp[n][index]<<endl; } return 0; }