合并神犇!!!

来给大家送水题了
image
洼,太水了,建议降黄
正解为dp。
状态转移方程为:

f[i]=f[j]+i−j−1
g[i]=sum[i]−sum[j]

双手奉上蒟蒻的伪代码

int main(){
    //输入
    //计算前缀和数组sum
    for(int i=1~n/*遍历*/){
        /*从i-1到1遍历*/ if(/*从a[j]加到a[i]大于合并前i-1个数最少合并的次数次后的最小值*/) break;
        //状态转移方程
    }
    //输出最小合并次数
}

O(n^2)
谁让这数据那么水