P1775

AKNOI的梓钦 · 2022-01-06 19:15:19 · 题解

分析！！

若最初的 l 堆石子和第 r 堆石子被合并成一堆，则说明 l ~ r 之间的每堆石子也已经被合并，这样 l 和 r 才有可能相邻。

因此，在任意时刻，任意一堆石子都可以用一个闭区间\left [ l,r \right ] 来描述，表示这堆石子是由最初的第 l ~ r 堆石子合并而成的，其重量为 {\textstyle \sum_{i=l}^{r}} A_i 。

另外，一定存在一个整数 k\left ( l\le k<r \right ) ，在这堆石子形成之前，先有第 l ~k 被合并成一堆，第 k+1 ~r 堆石子被合并成一堆，然后两堆石子才合并成 \left [ l,r \right] 。

对应到动态规划中，就意味着两个长度较小的区间上的信息向一个更长的区间发生了转移，划分点 k 就是转移的决策。

自然地，应该把区间长度 len 作为 DP 的阶段。

不过，区间长度可以有左端点到右端点表示出，即 len=r-l+1 。

代码（我知道你们只会看这个）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 305;
int a[N],f[N][N],sum[N],n;
int main(){
    scanf("%d",&n);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        f[i][i]=0;
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;++len){
        for(int l=1;l<=n-len+1;++l){
            int r=l+len-1;
            for(int k=l;k<r;++k){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            }
            f[l][r]+=sum[r]-sum[l-1];
        }
    }
    printf("%d",f[1][n]);
    return 0;
}