[Acwing] 算法提高课汇总一 动态规划-区间DP

区间DP

1.环形石子合并

题意 :
环状石子合并相邻的两堆,询问最大最小开销

思路 :
状态表示 :
f [ l ] [ r ] f[l][r] f[l][r]表示从 l l l开始到 r r r的花费

状态计算 :
f [ l ] [ r ] = m i n / m a x ( f [ l ] [ r ] , f [ l ] [ k ] + f [ k ] [ r ] + s [ r ] − s [ l − 1 ] ) f[l][r] = min/max(f[l][r],f[l][k]+f[k][r]+s[r]-s[l-1]) f[l][r]=min/max(f[l][r],f[l][k]+f[k][r]+s[r]−s[l−1])

因为是环形问题,我们考虑开两倍的空间用于存放

那么对于 i i i就对应 i + n − 1 i+n-1 i+n−1

code :

int n;
int w[N],s[N];
int f[N][N],g[N][N];
void solve()
{
    cin>>n;
    for(int i=1;i>w[i];
        w[i+n] = w[i];///两倍数组
    }

    for(int i=1;i