石子合并

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1365 字

将环形摆放的n堆石子每次合并相邻两堆，合并代

一本通
例

正文

/*
原题：石子合并（环形，求 n-1 次合并得分总和的最小值与最大值）
题意：将环形摆放的 n 堆石子每次合并相邻两堆，合并代价为两堆石子数之和，求总代价最小与最大。
思路：破环成链，长度扩为 2n；dp[i][j] 表示合并区间 [i,j] 的最小/最大代价，
      dp[i][j]=min/max{dp[i][k]+dp[k+1][j]}+sum(i..j)，枚举断点 k。
复杂度：时间 O(n^3)，空间 O(n^2)
易错点：环形需断环成 2n 长的链；答案取所有长度为 n 的区间 dp 值的最小（大）者。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<long long> a(2*n+1), s(2*n+1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++){
        s[i]=s[i-1]+a[i];
    }
    vector<vector<long long>> dmin(2*n+1, vector<long long>(2*n+1,0));
    vector<vector<long long>> dmax(2*n+1, vector<long long>(2*n+1,0));
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            dmin[i][j]=LLONG_MAX;
            dmax[i][j]=LLONG_MIN;
            long long sum=s[j]-s[i-1];
            for(int k=i;k<j;k++){
                dmin[i][j]=min(dmin[i][j], dmin[i][k]+dmin[k+1][j]+sum);
                dmax[i][j]=max(dmax[i][j], dmax[i][k]+dmax[k+1][j]+sum);
            }
        }
    }
    long long ansmin=LLONG_MAX, ansmax=LLONG_MIN;
    for(int i=1;i+n-1<=2*n;i++){
        ansmin=min(ansmin, dmin[i][i+n-1]);
        ansmax=max(ansmax, dmax[i][i+n-1]);
    }
    cout<<ansmin<<"\n"<<ansmax<<"\n";
    return 0;
}

石子合并

正文

一本通·提高篇的其它内容