3 条题解

  • 0
    @ 2025-4-13 19:37:12
    #include <vector>
    #include <climits>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        vector<int> a(2 * n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            a[i + n] = a[i]; // 处理环形数组
        }
    
        // 计算前缀和数组
        vector<long long> prefix(2 * n + 1, 0);
        for (int i = 1; i <= 2 * n; ++i) {
            prefix[i] = prefix[i - 1] + a[i - 1];
        }
    
        // 初始化动态规划数组
        const long long INF = 1e18;
        vector<vector<long long> > dp_min(2 * n, vector<long long>(2 * n, INF));
        vector<vector<long long> > dp_max(2 * n, vector<long long>(2 * n, -INF));
    
        for (int i = 0; i < 2 * n; ++i) {
            dp_min[i][i] = 0;
            dp_max[i][i] = 0;
        }
    
        // 动态规划填表
        for (int len = 2; len <= n; ++len) { // 合并的区间长度
            for (int i = 0; i <= 2 * n - len; ++i) { // 区间起点
                int j = i + len - 1; // 区间终点
                long long sum_ij = prefix[j + 1] - prefix[i];
    
                // 枚举分割点k
                for (int k = i; k < j; ++k) {
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum_ij);
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum_ij);
                }
            }
        }
    
        // 寻找所有可能的起点中的最优解
        long long min_score = INF, max_score = -INF;
        for (int i = 0; i < n; ++i) {
            int j = i + n - 1;
            min_score = min(min_score, dp_min[i][j]);
            max_score = max(max_score, dp_max[i][j]);
        }
    
        cout << min_score << endl;
        cout << max_score << endl;
    
        return 0;
    }
    
    

    没见过吧,那就点赞再走。

    求求了QAQ

    • 0
      @ 2022-8-21 19:27:17
      #include <iostream>
      #include <algorithm>
      #include <cstdio>
      #include <cstring>
      #include <string>
      #include <iomanip>
      #include <cmath>
      #include <queue>
      #include <map>
      #include <stack>
      #include <vector>
      using namespace std;
      #define long long LL
      const int N = 1e3+5;
      const int INF = 0x3f3f3f3f;
      int n,a[N],dp[N][N],minn = INF,sum[N],dp1[N][N],maxx;
      int main(){
      	cin >> n;
      	memset(dp,INF,sizeof(dp));
      	for (int i = 1;i<=n;i++){
      		cin >> a[i];
      		a[i+n] = a[i];
      	}
      	for (int i = 1;i<=2*n;i++){
      		sum[i] = sum[i-1] + a[i];
      		dp[i][i] = 0;
      	}
      	for (int i = 2;i<=n;i++){
      		for (int j = 1;j<=2*n-i+1;j++){
      			int endx = j + i - 1;
      			for (int k = j;k<endx;k++){
      				dp[j][endx] = min(dp[j][endx],dp[j][k] + dp[k+1][endx] + sum[endx] - sum[j-1]);
      				dp1[j][endx] = max(dp1[j][endx],dp1[j][k] + dp1[k+1][endx] + sum[endx] - sum[j-1]);
      			}
      		}
      	}
      	for (int i = 1;i<=n;i++){
      		minn = min(minn,dp[i][i+n-1]);
      		maxx = max(maxx,dp1[i][i+n-1]);
      	}
      	cout << minn << endl << maxx;
      	return 0;
      }
      
      • 0
        @ 2022-8-18 14:54:02

        '''和上一题十分类似,简单加点东西就好了。这里不多做解释。代码比较好理解。

        /*****************************************
        备注:
        ******************************************/
        #include <queue>
        #include <math.h>
        #include <stack>
        #include <stdio.h>
        #include <iostream>
        #include <vector>
        #include <iomanip>
        #include <string.h>
        #include <algorithm>
        using namespace std;
        #define LL long long
        const int N = 1e5 + 10;
        const int INF = 0x3f3f3f3f;
        int n;
        int dp[505][505];
        int f[505][505];
        int a[305];
        int sum[N];
        int main(){
        
        	cin>>n;
        	for(int i=1; i<=n; i++)
        	{
        		cin>>a[i];
        		a[i + n] = a[i];
        	}
        	for(int i=1; i<=2*n; i++)
        	{
        		sum[i] = sum[i - 1] + a[i];
        	}
        	for(int k = 2; k <= n; k++)
        	{
        		for(int l = 1; l + k - 1 <= 2 * n; l++)
        		{
        			int r = l + k - 1;
        			f[l][r] = INF;
        			for(int i = l; i < r; i++)
        			{
        				dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r] + sum[r] - sum[l - 1]);
        				f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1]);
        			}
        		}
        	}
        	int minn = INF;
        	int maxx = 0;
        	for(int i = 1; i <= n; i++)
        	{
        		maxx = max(maxx, dp[i][i + n - 1]);
        		minn = min(minn, f[i][i + n - 1]);
        	}
        	cout<<minn<<endl;
        	cout<<maxx<<endl;
        	
        
        	return 0;
        }
        
        • 1

        信息

        ID
        1639
        时间
        1000ms
        内存
        256MiB
        难度
        5
        标签
        递交数
        157
        已通过
        64
        上传者