Catshao

用户名：Catshao

访问量：28830

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7133
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

[ω] 最大子段乘积
浏览：108

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1472

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：547

你可能喜欢

此题极度卡常

　　作者: Catshao　　　　发表时间：2022-02-15 21:49:15 浏览：34　|　评论：1　

原题链接：[模板] 线性规划 & 分组背包

**数据目前没有 SPJ！也就是说只要你写法和我不同可能过不去。如果我的数据出锅了请联系我。**

--------------

说实话我也没想到测评机能这么慢……本机我 std 可以跑到 0.8s。

分组背包想必大家都会了吧 $$O(nmk)$$ 。这道题在此基础之上需要记录当前状态是由谁转移过来的。

然后你会发现你 TLE 了。

在代码前加一句

```cpp
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

```

然后你就过了。

实际测试中把 f 数组压成一维反而会变慢。估计是因为 $$a\_{i, j} \le 100$$ 卡进缓存了。

```cpp
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 105;
const int MAX_K = 100010;

int n, m, k, a[MAX_N][MAX_N], f[MAX_N][MAX_K], choose[MAX_N][MAX_K];

inline void max(int &x, int y, int &z, int w) {
    if (y > x) {
        x = y;
        z = w;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            f[i][j] = f[i - 1][j];
            for (int x = 1; x <= m; ++x) {
                if (j >= x) {
                    max(f[i][j], f[i - 1][j - x] + a[i][x], choose[i][j], x);
                } else {
                    break; // 重量单调递增
                }
            }
        }
    }
    cout << f[n][k] << endl;
    stack<int> s;
    int w = k;
    for (int i = n; i >= 1; --i) {
        s.push(choose[i][w]);
        w -= choose[i][w];
    }
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    return 0;
}
```

0.0分

1 人评分

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

　　评论区

Catshao

单纯形法应该是过不去了 qwq

2022-02-15 21:56:52

Catshao

TA的其他文章

你可能喜欢

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

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

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

字符串输入输出函数（Java代码）

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

此题极度卡常

评论区

精彩推荐

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

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

点我有惊喜！你懂得！

数列（C++代码）

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

大神老白（C语言代码）

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

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

Catshao

TA的其他文章

你可能喜欢

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

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

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

字符串输入输出函数 （Java代码）

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

此题极度卡常

评论区

精彩推荐

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

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

点我有惊喜！你懂得！

数列 （C++代码）

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

大神老白 （C语言代码）

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

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

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

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

字符串输入输出函数（Java代码）

　　评论区

数列（C++代码）

大神老白（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）