UVA1754 Posterize

题意

有一个长为 $n(\le 256)$ 的数组 $a$ ，第 $i$ 个数有权值 $b_i$ 。从中选取 $K$ 个点 $c_j$ ，把 $a$ 上的数都移过去，代价为 $\sum (a_i-c_j)^2\times b_i$ 。求最小代价。

题解

非常暴力的DP。用 $f[i][j]$ 表示前 $i$ 个数选了 $j$ 个点，其中第 $i$ 个点选的最小代价。预处理选取 $i,j$ 后 $(i,j)$ 区间移动的代价 $v[i][j]$ ，方程式为：

$$f[i][j]=\min f[k][j-1]+v[k][i]$$

然后枚举第一个取的和最后一个取的位置，中间暴力 $O(n^3)$ 转移即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=265;
ll n,k,a,s[N],f[N][N],v[N][N];

signed main()
{
    while (~scanf("%lld%lld",&n,&k))
    {
        memset(s,0,sizeof(s));
        for (ll i=1;i<=n;i++) a=read(),s[a+1]=read();
        for (ll i=1;i<=256;i++)
        {
            for (ll j=i+2;j<=256;j++)
            {
                ll mid=(i+j)>>1;
                v[i][j]=0;
                for (ll k=i+1;k<j;k++)
                {
                    if (k>mid) v[i][j]+=(j-k)*(j-k)*s[k];
                    else v[i][j]+=(k-i)*(k-i)*s[k];
                }
            }
        }
        for (ll i=1;i<=256;i++) //第一个取的位置
        {
            f[i][1]=0;
            for (ll j=1;j<i;j++) f[i][1]+=(i-j)*(i-j)*s[j];
        }
        for (ll j=2;j<=k;j++) //暴力转移
        {
            for (ll i=j;i<=256;i++)
            {
                f[i][j]=f[i-1][j-1];
                for (ll k=j-1;k<i-1;k++)
                {
                    f[i][j]=min(f[i][j],f[k][j-1]+v[k][i]);
                }
            }
        }
        ll ans=f[256][k];
        for (ll i=255;i;i--) //最后一个取的位置
        {
            ll cur=0;
            for (ll j=256;j>i;j--) cur+=(i-j)*(i-j)*s[j];
            ans=min(ans,f[i][k]+cur);
        }
        printf("%lld\n",ans);
    }
    return 0;
}