「Algospot」量化QUANTIZE

一道不难的DP题，主要是为了总结这类最优化题的思路；同时还学到了一个新操作

传送门：$>here<$

题意

给出一个长度为$N$的序列，要求最多使用s个数字进行量化（有损压缩），即代替原数字：使得量化后各个被代替的数与代替的数的差的平方之和最小。

数据范围：$n \leq 100, s \leq 10$

Solution

动态规划的常规思路

容易发现肯定选择数值相近的一些数字用一个数字取替代，所以肯定先排序。

排序完后就是一个简单的dp题了。$dp[i][j]$表示前$i$个数字，使用$j$个数字量化的最小误差。当前决策一定关于第$i$个数字有关，问题在于究竟这一段要多长。在枚举一个k，转移就很明显了：

$dp[i][j]=Min\{dp[k][j-1]+quantize(k+1,i)\}$

究竟用什么来做量化的值

问题转化为了如何求$quantize$函数。就这道题的范围来看，从最小到最大枚举也是没有问题的。但实际上有$O(1)$方法。

设我们选择$m$来量化，也就是说函数$y=\sum\limits_{i=l}^{r}(m-a[i])^2$最小。问题转化为求此函数的最小值。

这是个二次函数，所以展开后直接求导（或直接使用顶点公式），找到顶点的$x$坐标即可。

$y=\sum\limits_{i=l}^{r}(m-a[i])^2=(r-l+1)m^2-2m\sum\limits_{i=l}^{r}a[i]+\sum\limits_{i=l}^{r}a[i]^2$

当$y'=2(r-l+1)m-2\sum\limits_{i=l}^{r}a[i]=0$时

$m=\frac{\sum\limits_{i=l}^{r}a[i]}{r-l+1}$

这就是平均值！由此我们得到结论：当利用平均值来当量化值时，差的平方之和最小。

透过题解看本质

其实对于这类最优化dp问题，可以看做是递归问题。dp的本质是记忆化搜索，只不过可以利用递推来实现。当我搜到这一步时需要枚举来决策当前需要多长的一段来量化，而剩余的则不需要递归，而是直接利用之前做好的最优子结构。这就是dp为什么比dfs快了。其实dp就是暴力，它终究需要考虑所有需要且可能的情况。

my code

具体在实现的时候通过统计前缀和以及平方的前缀和来$O(1)$完成求解。注意把$m$代入求误差时也要利用前缀和。

注意平均值应该四舍五入。

/*By DennyQi 2018*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = ; int w = ; register char c = getchar();

    for(; c ^ '-' && (c < '' || c > ''); c = getchar());

    if(c == '-') w = -, c = getchar();

    for(; c >= '' && c <= ''; c = getchar()) x = (x<<) + (x<<) + c - ''; return x * w;

}

int T,N,s;

int a[MAXN],dp[MAXN][],sum[MAXN],ssqr[MAXN];

inline int calc(int l, int r, int m){

    int res = ;

    res += m*m * (r-l+);

    res += ssqr[r] - ssqr[l-];

    res -= *m*(sum[r]-sum[l-]);

    return res;

}

inline int quantize(int l, int r){

    int m = (sum[r]-sum[l-]) / (r-l+);

    return Min(calc(l,r,m), calc(l,r,m+));

}

inline int Solve(){

    sort(a+,a+N+);

    sum[] = ssqr[] = ;

    for(int i = ; i <= N; ++i){

        sum[i] = sum[i-] + a[i];

        ssqr[i] = ssqr[i-] + a[i] * a[i];

    }

    memset(dp,INF,sizeof(dp));

    for(int i = ; i <= s; ++i) dp[][i] = ;

    for(int i = ; i <= N; ++i){

        for(int j = ; j <= s; ++j){

            for(int k = ; k < i; ++k){

                dp[i][j] = Min(dp[i][j], dp[k][j-] + quantize(k+,i));

            }

        }

    }

    return dp[N][s];

}

int main(){

//    freopen(".in","r",stdin);

    T = read();

    while(T--){

        N = read(), s = read();

        for(int i = ; i <= N; ++i){

            a[i] = read();

        }

        printf("%d\n", Solve());

    }

    return ;

}

秒客网