HDU 3480 Division

发布于 13 天前  27 次阅读


题目链接

题意

有长度为 n 的序列,定义一个集合的代价是$(MAX-MIN)^2$,要求你找出 m 个集合,在满足下面图片的限制的情况下,使得总代价最小。

多组数据,每组数据 $n \leq 10^4,m \leq 5 \times 10^3$,保证答案在 int 范围内。

题解

观察题目 发现让你选取 M 个集合使得代价最小。
首先一个观察是,取得代价最小的方案一定是按照排序后按顺序取的,并且这些集合两两不交。
然后我们考虑排序后进行 dp:记前 i 段选了 j 个数的最小代价是 $f_{i,j}$,暴力转移就是枚举最后选择的一段区间,暴力转移方程:
$$f_{i,j} = min \{f_{i-1,k} + (a_i - a_{k+1})^2 \}$$
这样复杂度是 $O(n^2m)$ 显然过不去。于是我们来考虑进行斜率优化。
首先发现当前转移只与第二维上一次的状态有关,可以考虑滚动数组,即记 $g = f_{i-1}$,那么我们化简递推式,可以得到
$$f_{i} = min\{g_{k}+(a_i-a_{k+1})^2\}$$
套路地设如果 $j < k$ 且从 $j$ 转移更优,则有式子:
$$g_{j} +(a_i - a_{j+1})^2 < g_k + (a_i - a_{k+1})^2$$
化简一下:
$g_{j} +(a_i - a_{j+1})^2 < g_k + (a_i - a_{k+1})^2$
$\Rightarrow g_j+a_{j+1}^2-2a_ia_{j+1} < g_k + a_{k+1}^2 - 2a_ia_{k+1}$
$\Rightarrow g_j+a_{j+1}^2 - g_k-a_{k+1}^2 < 2a_i(a_{j+1}-a_{k+1})$
不妨令 $F_i = g_i-a_{i+1}^2$
$\Rightarrow F_j-F_k < 2a_i(a_{j+1}-a_{k+1})$
$\Rightarrow \frac{F_j-F_k}{a_{j+1}-a_{k+1}} > 2a_i$
当 $j$ 不比 $k$ 优时,满足 $\frac{F_j-F_k}{a_{j+1}-a_{k+1}} \leq 2a_i$,也可以写成 $\frac{F_k-F_j}{a_{k+1}-a_{j+1}} \leq 2a_i$。
然后直接上斜率优化就好了。具体见代码。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 10000+5;
int f[2][MAXN],n,m,aa[MAXN],now;

#define X(i) (aa[i+1])
#define Y(i) (f[now^1][i]+aa[i+1]*aa[i+1])

inline bool chkhead(int a,int b,int c){
    return (Y(b)-Y(a)) <= 2*(X(b)-X(a))*aa[c];
}

inline bool chktail(int a,int b,int c){
    return (Y(b)-Y(a))*(X(c)-X(b)) >= (Y(c)-Y(b))*(X(b)-X(a));
}

int q[MAXN],head,tail;

inline int calc(int i,int j){
    return f[now^1][j] + (aa[j+1]-aa[i])*(aa[j+1]-aa[i]);
}

inline void init(){
    CLR(q,0);head = tail = 0;CLR(f,0);CLR(aa,0);now = 0;
}

inline void Solve(int times){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n) scanf("%lld",aa+i);
    std::sort(aa+1,aa+n+1);
    now = 0;FOR(i,1,n) f[now][i] = (aa[i]-aa[1])*(aa[i]-aa[1]);
    FOR(i,2,m){
        now ^= 1;q[head = tail = 0] = 0;
        CLR(f[now],0);
        FOR(j,1,n){
            while(head < tail && chkhead(q[head],q[head+1],j)) head++;
            f[now][j] = calc(j,q[head]);
            while(head < tail && chktail(q[tail-1],q[tail],j)) tail--;
            q[++tail] = j;
        }
    }
    printf("Case %lld: %lld\n",times,f[now][n]);
}

signed main(){
    int T;scanf("%lld",&T);
    FOR(i,1,T) Solve(i);
    return 0;
}

一个OIer。