区间DP (1)

问题链接: 环形石子合并

思路: 区间DP

1. 区间处理
   题目中给出了一个环状区间, 如果考虑贪心算法, 可以找到反例; 如果对区间缺口进行枚举, 那么时间复杂度为.一种常用的优化技巧为复制一倍区间, 将环状区间转为链式区间存储, 枚举长度为的区间, 优化后的时间复杂度为.
2. 动态规划
   状态定义: f[l][r]表示将区间左端点为l至右端点r的石子进行合并的得分.
   状态转移: f[l][r]=min(f[l][r], f[l][k]+f[k+1][r]+sum[l][r])

算法设计

循环代码模板为:

for 区间长度(1 to n):
    for 区间左端点:
        {处理特判情况}
        for 区间断开点

pyhton版本

from typing import List
class Solution:
    def main(self, n:int, a:List[int]):
        fmax, fmin=[[0 for _ in range(2*n+1)] for _ in range(2*n+1)], [[float('inf') for _ in range(2*n+1)] for _ in range(2*n+1)]
        a.extend(a) # 将环形区间扩展一倍转为链式区间
        s=[0 for _ in range(2*n+1)]
        for i in range(1, 2*n+1):
            s[i]=s[i-1]+a[i-1]

        for LEN in range(1, n+1):
            l=1
            while l+LEN-1<=n*2:
                r=l+LEN-1
                if LEN==1: fmax[l][r]=fmin[l][r]=0
                else:
                    for k in range(l, r):
                        fmin[l][r]=min(fmin[l][r], fmin[l][k]+fmin[k+1][r]+s[r]-s[l-1])
                        fmax[l][r]=max(fmax[l][r], fmax[l][k]+fmax[k+1][r]+s[r]-s[l-1])
                l+=1

        res_min, res_max=float('inf'), 0
        for i in range(n): res_min, res_max=min(res_min, fmin[i][i+n-1]), max(res_max, fmax[i][i+n-1])

        print(res_min)
        print(res_max)

if __name__ == '__main__':
    n=int(input())
    a=list(map(int, input().split()))
    sol=Solution()
    sol.main(n, a)

c++版本

#include <bits/stdc++.h>
using namespace std;

const int N=405, INF=0x3f3f3f3f;
int n;
int s[N], w[N];
int f[N][N], g[N][N];

int main(){
    // 两条链断开后进行拼接
    cin>>n;
    for(int i=1; i<=n; ++i){
        cin>>w[i];
        w[i+n]=w[i];
    }
    // 预处理: 前缀和
    for(int i=1; i<=n*2; ++i) s[i]=s[i-1]+w[i];
    memset(f, 0x3f, sizeof f);
    memset(g, 0xcf, sizeof g);

    for(int len=1; len<=n; ++len)
        for(int l=1; l+len-1<=n*2; ++l){
            int r=l+len-1;
            if(len==1) f[l][r]=g[l][r]=0;
            else{
                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]);
                    g[l][r]=max(g[l][r], g[l][k]+g[k+1][r]+s[r]-s[l-1]);
                }
            }
        }
    int minv=INF, maxv=-INF;
    for(int i=1; i<=n; ++i){
        minv=min(minv, f[i][i+n-1]);
        maxv=max(maxv, g[i][i+n-1]);
    }
    cout<<minv<<endl<<maxv<<endl;

    return 0;
}