【第76题】继续刷区间八连刷（四）：随意混用，华丽丽爆零， [NOI1995] 石子合并

小码匠

发布于 2023-08-31 15:39:54

2010

发布于 2023-08-31 15:39:54

文章被收录于专栏：小码匠和老码农

对话

重点关注：对话过程，里面得坑，希望同学们千万别犯，本地OK，提交爆零，苦啊。。。

周六下午小码匠刷掉

[IOI2000] 邮局

晚上自然也不能放过她，继续查岗

继续画饼，有时候小码匠动不动管我这个老码农叫饼哥，画饼专业户啊。。。

小码匠也有些蒙圈，输出结果和样例一样，就是没分。

该我出山了，老码农我往往能画龙点睛。我注释掉3行代码，喜提40分

原因是这样，小码匠拷贝以前代码，混用cin和scanf，本地没问题，但提交到洛谷就挂了。

所以，千万不要混用cin和scanf，这是小码匠第二次因为混用挂掉题目。

总结：

不要混用cin和scanf

使用scanf和printf读写时，一定要注释掉下面代码

//    // 提升cin、cout效率
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);

题目

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P1880
- 参考题解：https://www.luogu.com.cn/problem/solution/P1880
标签：OI、动态规划、区间DP

题面

题目描述

在一个圆形操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

输入格式

数据的第 1 行是正整数 N，表示有N 堆石子。

第 2 行有 N 个整数，第 i 个整数

a_i

表示第 i 堆石子的个数。

输出格式

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

输入输出样例

输入 #1复制

4
4 5 9 4

输出 #1复制

43
54

说明/提示

1≤N≤100，0≤

a_i

≤20。

AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl '\n';
const int n = 305;
const int INF = 0x3f3f3f3f;

struct node {
    int maxn, minn;
};

void best_coder() {
    int m;
    scanf("%d", &m);
    vector<vector<node>> dp(n, vector<node>(n));
    vector<int> s(n);
    vector<int> a(n);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &a[i]);
        a[i + m] = a[i];
    }
    for (int i = 1; i < 2 * m; ++i) {
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 2; i <= m; ++i) {
        for (int j = 1; j + i - 1 <= m * 2; ++j) {
            int z = j + i - 1;
            dp[j][z].minn = INF;
            for (int k = j; k < z; ++k) {
                dp[j][z].minn = min(dp[j][z].minn, dp[j][k].minn + dp[k + 1][z].minn + s[z] - s[j - 1]);
                dp[j][z].maxn = max(dp[j][z].maxn, dp[j][k].maxn + dp[k + 1][z].maxn + s[z] - s[j - 1]);
            }
        }
    }
    node ans = {-1, 0x7f7f7f7f};
    for(int i = 1; i <= m; ++i) {
        ans.maxn = max(ans.maxn, dp[i][i + m - 1].maxn);
        ans.minn = min(ans.minn, dp[i][i + m - 1].minn);
    }
    printf("%d\n%d", ans.minn, ans.maxn);
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);

    // freopen("xxx.in", "r", stdin);
    // freopen("xxx.out", "w", stdout);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // fclose(stdin);
    // fclose(stdout);

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-10，如有侵权请联系 cloudcommunity@tencent.com 删除