十五月明

用户名：dotcpp0605328

访问量：5435

签　名：

等　　级
排　　名	319
经　　验	5465
参赛次数	0
文章发表	87
年　　龄	18
在职情况	学生
学　　校	曲阜师范大学
专　　业	人工智能

　　自我简介：

Easy

TA的其他文章

信息学奥赛一本通T1346-亲戚(relation) 并查集此题有毒
浏览：7

信息学奥赛一本通T1347-格子游戏并查集
浏览：5

团伙(group) 并查集
浏览：58

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

石子合并区间DP+破环成链+max和min

　　作者: 十五月明　　　　发表时间：2024-10-26 16:12:20 浏览：5　|　评论：0　

原题链接：信息学奥赛一本通T1569-石子合并

#include <bits/stdc++.h>
    using namespace std;
    const int N = 1100;
    int f1[N][N] = {0}; // 用于存储最大得分
    int f2[N][N] = {0}; // 用于存储最小得分
    int a[N]={0};
    int sum[N]={0}; // 存储前缀和，用于快速计算区间和
    
    int main() {
        int n; 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 len = 1; len <= n; len++) {
            for (int i = 1; i + len - 1 <= 2 * n; i++) {
                int j = i + len - 1;
                if (i == j) {
                    f2[i][j] = 0; // 当 i 和 j 相同时，没有选择任何石头，最小得分为0
                } else {
                    f2[i][j] = 1e9; // 初始化为一个很大的数，表示不可能的得分
                }
                for (int k = i; k < j; k++) {
                    int totalStones = sum[j] - sum[i - 1]; // 直接使用sum数组计算区间石子总数
                    f1[i][j] = max(f1[i][j], f1[i][k] + f1[k + 1][j] + totalStones); // 计算最大得分
                    f2[i][j] = min(f2[i][j], f2[i][k] + f2[k + 1][j] + totalStones); // 计算最小得分
                }
            }
        }
        int maxScore = 0; // 最大得分
        int minScore = 1e9; // 最小得分
        for (int i = 1; i <= n; i++) {
            maxScore = max(maxScore, f1[i][i + n - 1]);
            minScore = min(minScore, f2[i][i + n - 1]);
        }
        cout << minScore << endl << maxScore << endl;
        return 0;
    }

在这段代码中，f1[i][j] 表示从第 i 个石头到第 j 个石头的最大得分。对于 f1，不需要像 f2 那样在 i == j 时初始化为一个特定值，因为 f1[i][j] 的计算方式与 f2[i][j] 不同。
在动态规划的转移方程中，f1[i][j] 是通过合并子区间的最大得分来计算的。即使在 i == j 的情况下，f1[i][j] 的值也会在后续的迭代中被正确地更新。这是因为 f1[i][j] 的计算依赖于子区间的得分，而这些子区间的得分已经在之前的迭代中被计算和更新过了。

具体来说，f1[i][j] 的转移方程是这样的：
f1[i][j] = max(f1[i][j], f1[i][k] + f1[k + 1][j] + totalStones);

这里，totalStones 是从第 i 个石头到第 j 个石头的总数。即使在 i == j 的情况下，这个方程仍然有效，因为 totalStones 会是0，而 f1[i][i] 的值会在后续的迭代中通过合并其他子区间的得分来更新。
因此，对于 f1，不需要在 i == j 时初始化为0或其他特定值，因为它的值会在动态规划的过程中被自然地更新。而对于 f2，由于它的计算方式不同，需要在 i == j 时初始化为一个特定值，以避免错误的转移。

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

十五月明

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

人见人爱A+B （C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

石子合并区间DP+破环成链+max和min

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

母牛的故事（C语言代码）

多输入输出练习1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

A+B for Input-Output Practice （C语言代码）

C二级辅导-公约公倍（C语言代码）

【计算直线的交点数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

十五月明

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

人见人爱A+B （C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

C语言训练-求1+2!+3!+...+N!的和 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

石子合并 区间DP+破环成链+max和min

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

母牛的故事 （C语言代码）

多输入输出练习1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

A+B for Input-Output Practice （C语言代码）

C二级辅导-公约公倍 （C语言代码）

【计算直线的交点数】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

石子合并区间DP+破环成链+max和min

　　评论区

母牛的故事（C语言代码）

C二级辅导-公约公倍（C语言代码）

【计算直线的交点数】（C语言代码）