Informatics Olympiad all in one 1274: [example 9.18] merging pebbles | Luogu p1775 pebbles merging (weakened version)

【 Topic link 】

ybt 1274：【 example 9.18】 Merge stones
Luogu P1775 Stone merging （ Weak version ）

【 Topic test site 】

1. Dynamic programming ： Interval dynamic gauge

【 Their thinking 】

1. State definition

aggregate ： A plan to merge all the stones
Limit ： The interval of the stones to be merged in the original sequence
attribute ： score
Conditions ： Minimum
statistic ： score
State definition ：dp[i][j]： Change the number of i To the first j In all the schemes where the stones are combined into one pile , The score of the scheme with the lowest score .
The initial state ： Since the minimum value is required later , So first put dp The array is initialized to infinity .
dp[i][i]： Will be the first i Pile up to the third i The heap is merged into 1 Pile up , No need to operate , No score , The score is 0. therefore ：dp[i][i]=0.

2. State transition equation

Note that the prefix and array of the number of stones are s, The first i Pile up to the third j The sum of the number of rockfill is s[j]-s[i-1].
aggregate ： Will be the first i To the first j A plan to combine stones into a pile
In a pile of money , The first i To the first j The rockfill must have been merged into two adjacent left and right piles through some scheme . Then the two piles are combined into one pile , The score of this merger is i To the first j The sum of the number of stones s[j]-s[i-1].
According to before the last merger , Two piles of stones " Split position " To split the set

• The left pile of stones is the No i Pile up , The minimum score of the combined left rockfill is dp[i][i]. The right pile of stones is the No i+1 Pile up to the third j A pile of stones , The minimum score for merging into the right rockfill is dp[i+1][j], Plus the last combined score , That is the second i To the first j Minimum score for heap merge ：dp[i][j] = dp[i][i]+dp[i+1][j]+s[j]-s[i-1]
• The left pile of stones is the No i Pile up to the third i+1 A heap that is merged into a heap , The minimum score of the combined left rockfill is dp[i][i+1]. The right pile of stones is the No i+2 Pile up to the third j A pile of stones , The minimum score for merging into the right rockfill is dp[i+2][j], Plus the last combined score , That is the second i To the first j Minimum score for heap merge ：dp[i][j] = dp[i][i+1]+dp[i+2][j]+s[j]-s[i-1]
  …
• The left pile of stones is the No i Pile up to the third j-1 A heap that is merged into a heap , The minimum score of the combined left rockfill is dp[i][j-1]. The right pile of stones is the No j Rubble , The minimum score for merging into the right rockfill is dp[j][j], Plus the last combined score , That is the second i To the first j Minimum score for heap merge ：dp[i][j] = dp[i][j-1]+dp[j][j]+s[j]-s[i-1]
• Take the minimum value in all the above cases
• Sum up , Split position k from i Loop to j-1,dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+s[j]-s[i-1])

When traversing, you need to traverse all of the whole sequence i To j Subsegment . Outer sub segment length len from 2 To n, The left end of the sub segment is i, On the right is i+len-1,i from 1 Start the cycle from small to large until the right end i+len-1 by n until . Find out j = i+len-1 Indicates the right end .
Finally, output the second 1 Pile up to the third n The minimum score that can be obtained by heap merging dp[1][n].

【 Solution code 】

solution 1： Interval dynamic gauge

#include<bits/stdc++.h>
using namespace std;
#define N 305
int n, a[N], dp[N][N], sum[N];//sum[i]: The prefix and  1~i And  
int main()
{
    
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
    
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }
    memset(dp, 0x3f, sizeof(dp)); 
    for(int i = 1; i <= n; ++i)
        dp[i][i] = 0;
    for(int len = 2; len <= n; ++len)// Interval length  
    {
    
        for(int i = 1; i+len-1 <= n; ++i)// Left end point  
        {
    
            int j = i+len-1;// Right endpoint  
            for(int k = i; k < j; ++k)// In two parts ：i~k, k+1~j 
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    }
    cout << dp[1][n];
    return 0;
}