来给大家送水题了
洼,太水了,建议降黄
正解为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)
谁让这数据那么水