算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目简介:
    给你一个序列A,请你把序列A分成连续K个子段,每个子段的代价是 sum(A[i]*A[j]) 其中 i < j。请问如何分组使代价最小。
    数据范围|A|,K <1000

吐槽:
    cppblog的editor可真是不咋的...  昨天弄了一下午LyX,想用XeTeX编译,结果屡屡失败。用vim写的TeX文档是可以用XeTeX编译并正确显示中文的。但是不知道为什么用LyX写就不可以.... 有没有TeX高手来指点一下啊...

解法分析:
    首先状态转移方程比较容易想到:DP[i][k]表示前i项分成了k组,那么有DP[i][k] = max(DP[j][k-1]+cost[j+1][i])对所有 j < i;
    这是一个2D/1D的方程,时间复杂度是O(n^3),对于n = 1000来说必然超时,需要优化...
    (A[j]+...+A[i])^2 = A[j]^2 + A[j+1]^2 + ... + A[i]^2 + 2* cost[j][i]; (没有TeX写这个就是不爽啊)
    于是乎 cost[j+1][i] = ((sum[i]-sum[j])^2 - suma[i] + suma[j])/2 = -sum[i] * sum[j] + (suma[j] - sum[j]^2)/2 + (sum[i]^2 - suma[i])/2;
    终于把这个转成只和 i,j相关的表达式了, 可以斜率优化了:
    X(j) = sum[j]
    Y(j) = (suma[j] - sum[j]^2)/2 + dp[j][k-1];
    C(i) = (sum[i]^2 - suma[i])/2
    我们要求的是 dp[i][k] = -sum[j]*X(j) + Y(j) + C(i);
    移项得 Y(j) = X(j)*sum[j] + dp[i][k] - C(i) 转成了线性规划问题。 不难想到最优解一定在凸包上。
    而且X,Y是单调的,可以用栈维护凸包。斜率是单调的,可以用队列维护最优决策。
代码部分:
#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;
#define re(i,n) for(int i = 0; i< n; i++)
const int N = 1001;
typedef long long ll;
ll dp[N][N];
ll num[N],pos[N][2],sum[N],suma[N];
int Q[N];
bool cal(int p0, int p1 , ll k){
return pos[p1][1] - pos[p0][1] < k * ( pos[p1][0] - pos[p0][0]);
}
ll cross( int p0, int p1, int p2){
return (pos[p0][0] - pos[p1][0] ) * ( pos[p0][1] - pos[p2][1] ) - ( pos[p0][1] - pos[p1][1]) * ( pos[p0][0] - pos[p2][0] );
}
int main(){
int n,m ;
while(~scanf("%d%d",&n,&m) && n){
re(i,n)
scanf("%lld",&num[i]);
re(i,n) sum[i] = (i == 0 ? 0 : sum[i-1]) + num[i];
re(i,n) dp[i][0] = ( i == 0 ? 0 : dp[i-1][0] + num[i] * sum[i-1]);
re(i,n) suma[i] = (i == 0 ? 0 : suma[i-1])+ num[i] * num[i];
for(int j = 1; j<=m ; j++) {
int head = 0 ,tail =0 ;
for(int i = j; i < n ; i++){
pos[i][0] = sum[i-1]; pos[i][1] = dp[i-1][j-1] + (suma[i-1] + sum[i-1]*sum[i-1])/2;
while(tail - head > 1 && cross(Q[tail-2] , Q[tail-1], i) <= 0) tail --;
Q[tail ++ ] = i;
while(tail - head > 1 && cal(Q[head], Q[head +1 ] , sum[i]) ) head ++;
dp[i][j] = pos[Q[head]][1] - pos[Q[head]][0] * sum[i] + (sum[i]*sum[i] - suma[i])/2;
}
}
cout<< dp[n-1][m] <<endl;
}
}
posted on 2012-04-24 14:51 西月弦 阅读(904) 评论(3)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: hdu 2829 动态规划+斜率优化
2012-08-23 21:18 | ZeroClock
学习了。思路和代码都很飘逸...可以加你好友吗?  回复  更多评论
  
# re: hdu 2829 动态规划+斜率优化
2012-08-24 12:43 | 西月弦
@ZeroClock
可以哦,我的QQ和姓名在首页上.
我在CF和TC的ID是hanfei19910905  回复  更多评论
  
# re: hdu 2829 动态规划+斜率优化[未登录]
2013-05-04 15:57 | 123
于是乎 cost[j+1][i] = ((sum[i]-sum[j])^2 - suma[i] + suma[j])/2 = -sum[i] * sum[j] + (suma[j] - sum[j]^2)/2 + (sum[i]^2 - suma[i])/2;
这里是不是化错了。。sum[j]是正的,到了后面就变成负的了。这题我也差不多是类似做法,不过我没有把cost化开来。不知道哪里有问题,所以便来google了。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理