[interval DP] stone consolidation

subject

 282. Stone merging - AcWing Question bank

 AcWing 282. Stone merging （ Section DP Detailed analysis of template questions ） - AcWing

explain

• State means ：f(i,j) It means that you will i To j A collection of schemes combined into a pile , The attribute is min
• State calculation ：i<j when ,f(i,j)=min(f(i,k)+f(k+1,j)+s[j]-s[i-1]  i=j when ,f(i,i)=0
• The first layer of the loop is the enumeration interval length , The second dimension is fixed i The location of , Ensure that each state is calculated to
• The final answer is （1~n） Total interval of , namely f(1,n)

Code segment

Section DP Templates

for (int i = 1; i <= n; i++) {
    dp[i][i] =  Initial value 
}
for (int len = 2; len <= n; len++)           // Interval length 
    for (int i = 1; i + len - 1 <= n; i++) { // Enumeration starting point 
        int j = i + len - 1;                 // Interval end point 
        for (int k = i; k < j; k++) {        // Enumerate split points , Construct the state transition equation 
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }

#include<iostream>
using namespace std;
const int N=310;
int a[N],s[N],f[N][N],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=a[i]+s[i-1];
    }
    for(int i=1;i<=n;i++)
    f[i][i]=0;
    for(int len=2;len<=n;len++)
    for(int i=1;i+len-1<=n;i++)
    {
        int j=i+len-1;
        f[i][j]=1e9;
        for(int k=i;k<j;k++)
        {
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    }
    cout<<f[1][n]<<endl;
    
}