区间DP

3.区间DP

AcWing 282. 石子合并

实现思路：

• f(i,j)表示将第i堆到第j堆石子合并为一堆时的最小代价
• 状态划分：选一个分割点k，将ik，k+1j这两个堆（两个区间）的石子合并，然后加上两个区间堆的总合并代价（采用前缀和计算区间i到j的值，s[j]-s[i-1]）。
• 初始从枚举区间长度开始（即石子堆数，实际作为不同的区间划分情况），区间长度len从2到n枚举(从2开始是因为，若区间长度只有1的话，没必要合并了)
• 然后枚举左端点i，从1到i+len-1
• k从左端点i开始枚举，比如k=i+1时，区间被分割为(i,i+1)，(i+2,i+len-1)，左边区间就一堆，右边区间len-1堆
• 状态转移方程：f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1])

更详细说明：AcWing 282. 石子合并 - AcWing

#include <iostream>
#include <algorithm>
using namespace std;
const int N=310;
int n;
int s[N];//求区间前缀和 
int f[N][N];
int mian(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];//同时计算前缀和
    }
    
    for(int len=2;len<=n;i++){//枚举区间长度（石子堆数）
        for(int i=1;i+len-1<=n;i++){//枚举左端点
            int l=i,r=i+len-1;
            f[l][r]=0x3f3f3f3f;//代价先初始化为无穷大
            for(int k=l;k<=r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    
    cout<<f[1][n]<<endl;
    
    return 0;
}