题面:
传送门
思路:
依然是一道很明显的区间 dp
我们设 $dp\left[i\right]\left[j\right]$ 表示前 $j$ 个节点分成了 $i$ 块的最小花费,$w\left[i\right]\left[j\right]$ 表示把闭区间 $\left[i,j\right]$ 放在一起产生的价值
那么转移就比较明显了:
$dp\left[i\right]\left[j\right]=min\left(dp\left[i-1\right]\left[k-1\right]+w\left[k\right]\left[j\right]\right)$
$w$ 可以用前缀和维护以后 $O\left(1\right)$ 计算, 因为:
$w\left[i\right]\left[j\right]=\left(\left(\sum_{k=i}^{j}k\right)^2-\sum_{k=i}^{j}k^2\right)\div 2$
这样我们得到了一个复杂度为 $O\left(n^2 m\right)$ 的 dp, 但是解决这道题还不够
把 w 函数的表达式展开可以发现, w 满足四边形不等式, 因此把里层枚举 k 的那部分优化掉就好了
- Code:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define ll long long
- #define inf (1ll<<60ll)
- using namespace std;
- inline ll read(){
- ll re=0,flag=1;char ch=getchar();
- while(ch>9||ch<0){
- if(ch==-) flag=-1;
- ch=getchar();
- }
- while(ch>=0&&ch<=9) re=(re<<1)+(re<<3)+ch-0,ch=getchar();
- return re*flag;
- }
- ll n,m,a[1010],sum[1010],sqr[1010],s[1010][1010],dp[1010][1010];
- ll w(ll l,ll r){
- return ((sum[r]-sum[l-1])*(sum[r]-sum[l-1])-(sqr[r]-sqr[l-1]))/2ll;
- }
- int main(){
- ll i,j,k,tmp;
- while((n=read())&&(m=read())){
- m++;
- for(i=1;i<=n;i++)
- a[i]=read(),sum[i]=sum[i-1]+a[i],sqr[i]=sqr[i-1]+a[i]*a[i];
- for(i=1;i<=n;i++) dp[1][i]=w(1,i),s[1][i]=1;
- for(i=2;i<=m;i++){
- s[i][n+1]=n;
- for(j=n;j>i;j--){
- dp[i][j]=inf;
- for(k=s[i-1][j];k<=s[i][j+1];k++){
- if((tmp=dp[i-1][k-1]+w(k,j))<dp[i][j]){
- dp[i][j]=tmp;s[i][j]=k;
- }
- }
- }
- }
- printf("%lld\n",dp[m][n]);
- }
- }
来源: http://www.bubuko.com/infodetail-2530534.html