题目
Description
给定一正整数序列，例如：4，1，2，3，在不改变数的位置的条件下把它们相加，并且用括号来标记每一次加法所
得到的和。例如：（（4+1）+ （2+3））=（（5）+（5））=10。除去原数不4，1，2，3之外，其余都为中间结果
，如5，5，10，将中间结果相加，得到：5+5+10=20，那么数20称为此数列的一个代价，若得到另一种算法：（4+
（（1+2）+3））=（4+（（3）+3））=（4+（6））=10，数列的另一个代价为：3+6+10=19。若给出N个数，可加N-
1对括号，求出此数列的最小代价。
注：结果范围不超出longint.
Input
第一行为数N(1≤N≤200)
第二行为N个正整数，整数之间用空格隔开。.
Output
输出仅一行，即为最少代价值。
Sample Input
4 4 1 2 3
Sample Output
19
思路
首先这是一道经典的dp题；
那么d[i][j]表示i-j的最小代价，sum[i][j]是i-j每个石头的代价；
答案就是dp[1][n]了;
那么每一次合并i-j就需要加上i-j的权值代价；
dp[1][3]=min(dp[1][1]+dp[2][3]+sum[1][3],dp[1][2]+dp[3][3]+sum[1][3]);
所以我们需要枚举断开的位置k，i-j的合并就是i-k的合并加上k+1-j的合并再加上代价；
所以转移方程就是：
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
sum是前缀和；
然后枚举len长度，i起点，k断开的位置；
为什么不是先枚举i起点，在枚举j终点呢？
for(ll i=1;i<=n;i++)
for(ll j=i+1;j<=n;j++）
for(ll k=i;k<j;k++）
假如求出dp[1][2],然后枚举到dp[1][3]=dp[1][1]+dp[2][3] ；
然鹅dp[2][3]还未求出，所以我们需要枚举区间长度；
从区间长度小枚举到区间长度大，这样算长度大的区间时，访问小区间，小区间就有答案；
所以要枚举len长度，i起点，k断开的位置；
代码
#include<bits/stdc++.h> typedef long long ll; using namespace std; inline ll read() { ll a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();} return a*f; } ll n; ll dp[2001][2001],a[2001],s[2001]; int main() { n=read(); for(ll i=1;i<=n;i++) a[i]=read(); for(ll i=1;i<=n;i++)//计算前缀 s[i]=s[i-1]+a[i]; for(ll len=2;len<=n;len++)//枚举区间长度，len=1没什么意义额 for(ll i=1;i<=n-len+1;i++) { ll j=i+len-1; dp[i][j]=1<<30;//因为答案是求最小值，但是数组一开始都为0，答案也会为0，所以我们需要统计时改为最大值 for(ll k=i;k<j;k++) dp[i][j]=min(dp[i][k]+dp[k+1][j]+s[j]-s[i-1],dp[i][j]);//转移方程 } // for(ll i=1;i<=n;i++) // for(ll j=i+1;j<=n;j++) // { // dp[i][j]=1<<30; // for(ll k=i;k<j;k++)//假如求出dp[1][2],然后枚举到dp[1][3]=dp[1][1]+dp[2][3] // { //dp[2][3]还未求出，所以我们需要枚举区间长度 // dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j])+s[j]-s[i-1]; // cout<<dp[i][j]<<endl; // } // } //不要在意上面隐了的代码 printf("%lld ",dp[1][n]); }
写的不好，多多谅解