[HNOI2008]玩具装箱toy
YYY
posted @ 2015年7月09日 19:01
with tags
DP
, 511 阅读
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
这道题貌似可以用斜率优化，不过不用也行，利用决策单调性同样可以设计出O(nlogn)的算法..
首先可以很容易得到朴素的状态转移方程:(f(x)表示只装前x个玩具的最优解)
f(x) = min{f(k) + cost(k + 1,x)}
其中,cost(i,j)为把[i,j]这个区间内的玩具装到一个箱子里的代价:cost(i,j) = (Sj - Si + j - i - T)^2
其中,Sx = Σ(i = 1,j)Ci，Ci即为第i个箱子的长度
我们可以很容易发现，对于j > i,若cost(k,j) > cost(k,i),那么一定有cost(k,j + 1) > cost(k,i)(原因是cost(k,x)的函数图像开口向上且只有一个极值),而对于j > i,也有若f(j) > f(i),那么f(j + 1) > f(i)(因为f(x)是由cost(i,j)定义的)
也就是说，若f(j)的最优决策是f(i),那么f(j + 1)的最优决策也是f(i)
因此我们可以维护一个序列g(x),表示状态x的最优决策对应的状态估计值，当我们得到f(i)的具体值后，若对于某一个k,有对于k而言，f(i)比f(g(k))更优，那么我们可以用i去更新g(k)(k>i)的值，一定可以找到这样一个k，使得g(k')（k' >= k)都可以用i来更新，而且g(k'')(k''<k)都不可以用i来更新，可以二分答案找到这个k,每一次的时间复杂度为O(logn)
当我们枚举到i时，它当前的最优决策对应的状态估计值就是它当前的最优决策对应的状态，然后我们就用它去更新它后面的元素的g函数值,至于这个区间更新，可以随便找个数据结构啥的来维护一下，这样一共n个状态，每个状态更新后面的状态所需时间为O(T*logn),T为区间更新所花的时间，因此最后这道题的时间复杂的即为O(n*T*logn)
完整代码如下:
#include <stdio.h>
#include <iostream>
typedef long long Long;
const int N = 50000;
int n = 0;
Long L = 0;
Long a[N + 100];
Long f[N + 100];
struct sol
{
int n;
int l;
int r;
sol()
{}
sol(int _l,int _r,int _n)
{
l = _l;
r = _r;
n = _n;
}
};
sol q[N + 100];
int head = 1;
int tail = 0;
Long S[N + 100];
Long pow2(Long a)
{
return a * a;
}
Long pri(int j,int i)//对于i点，决策j的代价
{
return f[j] + pow2(S[i] - S[j] + i - j - 1LL - L);
}
int find(sol s1,int s2)
{
int low = s1.l;
int high = s1.r;
int mid = 0;
while(low <= high)
{
mid = ((low + high) >> 1);
if(pri(s2,mid) < pri(s1.n,mid))
high = mid - 1;
else low = mid + 1;
}
return low;
}
int main()
{
std::cin>>n>>L;
for(int i = 1;i <= n;i++)
{
std::cin>>a[i];
S[i] = S[i - 1] + a[i];
}
q[++tail] = sol(0,n,0);
for(int i = 1;i <= n;i++)
{
while(i > q[head].r)
head++;
f[i] = pri(q[head].n,i);
if(head > tail || pri(i,n) < pri(q[tail].n,n))
{
while(head <= tail && pri(i,q[tail].l) < pri(q[tail].n,q[tail].l))
tail--;
if(head <= tail)
{
int z = find(q[tail],i);//z点：新决策好
q[tail].r = z - 1;
q[++tail] = sol(z,n,i);
}
else q[++tail] = sol(i,n,i);
}
}
std::cout<<f[n]<<std::endl;
return 0;
}
评论 (0)
