问题标题: 新小说：《酷町世界》

酷町世界

第1回 酷町堂的入口
2021年7月10日9:50，酷町堂华地校区
“下面，我们来学习一下栈。栈是一种插入和删除受限制的线性表，大家记住了吗？”沈吴敏老师温文尔雅地说道，他正在上普及组冲刺班华地1班。
就在这时，只听突然地“轰”的一声。沈老师大窘，急忙忙地冲刺到爆炸声的源头——前台。前台的几台电脑被完全炸烂，惨不忍睹，几个前台的教务老师和正在喝茶的葛老师全被炸晕过去，横七竖八地趴在地上，但他们一点伤痕都没有。
“奇怪，怎么回事？”沈老师迅速拨打了110、119和120。
几分钟后，救援队都到了楼下，但是，他们都反映，他们被一个奇怪的空气墙阻隔，门、窗都进不了酷町堂的校区。对此，救援队也无能为力了，因为他们从来没有见过这种情况。这时，突然响起了歌声：“蓝蓝的天上白云飘”歌声戛然而止。他们不明白怎么回事，便尝试性地抬头看了一下天空：真蓝啊！天上，白云构成“只有酷町堂学员或老师才能进入本幢楼，没有闯过关卡不能出来”的字样。
救援队决定召集酷町堂学员，并选出一些勇士闯关。
过了很长时间………………终于召集了队伍 
我们来看一下这些勇士的名字吧！
葛新（指导教师）、沈吴敏（联席指导教师）、岳要举（联席指导教师）、臧鸿志（联席指导教师）、包涵宇（队长）、黄子阳（副队长）、侯平仄（副队长）、曹灿阳（副队长）、王泽宇、张帆、李泽远、宣海宁、江子周、蔡乐毅、沙宸安、王子逸、吴庞茂旭、王一帆、陈曦。
这时，一个4维传送通道映入眼帘，大家排成了一个队列，走了进去。
传送通道里真是一番风景！大家漂浮在里面，各种编程的元素在里面鳞次栉比地呈现，别有一番乐趣。大专家正在找：#include <bits/stdc++.h> cout<<"Hello, World!"; for(int i=1;i<=n;i++){} priority_queue<int,vecotor<int>,greater<int> > q;……笑声传遍了整个通道。
整个通道的前方，出现了一道亮光，后面不见入口，勇士们听不见啦啦队的呼唤声，只感觉放松以后，非常严峻的考验正在等着他们…… 

附录 任务
YYYY年MM月DD日HH时MM分    酷町世界
穿过通道，是一个美丽的小世界。此地有茂林修竹，鸟语花香，奇山怪柏，无不成趣。麋獐猿马，无不惬意。真个好地方！
这时，三个举止文雅，有飘飘之度的仙人从天上降下，他们介绍道：“我们是酷町堂的三大使者，分别是酷町猫，酷町侠和酷丁。”突然，掌声沸腾，非常热闹。
他们的声音突然放低了：“你们来到这个世界，是要和科丁乐的一支战队PK的，不是来玩的，不过这条挑战路上，有非常多的挫折、陷阱和坑，PK的形式不是你们想象的考试的形式，而是各种有趣的游戏的形式，还有许多惩罚，加油吧！少年！不要被困难打倒！解救酷町堂就靠你们了！按照规则，指导教师可以在中场休息和几场比赛的间隔时指导队员，但不能参与比赛。”

大家听罢，脊背突然一凉，五脏六腑都紧张得如同滚烫的烤红薯，这只战队，究竟能不能胜利，经历了什么磨难，且听下回分解。

第2回    入门测
这只整装待发的战队，来到了城门吊桥的入口，在他们旁边，是科丁乐的战队。
王泽宇和张帆一看，喝，科丁乐战队的队长是2021年小学组省赛的状元！ 
酷町侠穿着一件颇有风度的披风，说：“现在进行入门测，每一只战队被分配了一套试卷，每只战队先从各自的试题卷中选择ABC三题中的1题，先AC的队伍直接通关，后AC的队伍需要再做一题，只有所有题目都AC了才能通关。每道题必须一次AC，第一题限时10分钟。”
比赛开始了，包涵宇选了A题，题目是：

牛年吹牛    时间限制：1000毫秒
题目描述 Description
最近在泰迪的家乡有一个叫“牛年吹牛”的比赛，有N名选手参加了这个比赛，比赛非常激烈。
现在的问题是：
这N个竞争者的排名结果有多少种。排名允许并列。
由于答案将非常大，您可以只输出答案MOD 20090126。
以下是当 N = 2，两个选手参加比赛时，有以下3种结果：

第一名：1号；第二名：2号
第一名：2号；第一名：1号
第一名：1号和2号并列
输入描述 Input Description
第一行将包含T（T<=20000000），接下来T行
每行一个整数N（N<=8000），表示人数

输出描述 Output Description
T行，每行对应一个答案

样例输入 Sample Input
2
2
3
 
样例输出 Sample Output
3
13
数据范围及提示 Data Size & Hint
数据增强！

这道题的数据增强了，做起来有些许麻烦。“这个DP我定义好了，现在就差优化了。”“降维？”“怎么降？”…………
曹灿阳、王泽宇、包涵宇冥思苦想后，在距离时间到还有15秒时，提交到评测端。
只听见超级计算机风机吹动的声音，大家的脸烫得宛如烤红薯，红得犹如喝多了。
评测结果出来了：Accepted    100分
曹灿阳擦了擦头上的汗，终于放下了紧张的心。
“现在请做第二题。”酷町侠从天而降。
“什么？”大家惊慌了，“还有第二题？”
“你们也是真够倒霉的，他们选的题目是用两种方法写不降维的完全背包，你们选到了这么难的题目。”
曹灿阳、王泽宇、张帆想：“完全背包的两种写法不就是
for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        for(int k=0;k<=j/v[i];j++){
            f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
        }
    }
}
cout<<f[n][m];
和
for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        if(j>=c[i])
            f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
        else
            f[i][j]=f[i-1][j];
        }
    }
}
cout<<f[n][m];
吗！写出来，不就是有手就行吗！”
话不多说，第二题很快就呈现了。限时30分钟。

方格取数（number）     时间限制：1000毫秒

题目描述 Description
设有 n × m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经 过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

输入描述 Input Description
第 1 行两个正整数n, m。
接下来 n 行每行 m 个整数，依次代表每个方格中的整数。

输出描述 Output Description
一个整数，表示小熊能取到的整数之和的最大值。

样例输入 Sample Input
【样例 1 输入】
3 4
1 -1 3 2
2 -1 4 -1 
-2 2 -3 -1
【样例 2 输入】
2 5
-1 -1 -3 -2 -7 
-2 -1 -4 -1 -2
样例输出 Sample Output
【样例 1 输出】
9
【样例 2 输出】
-10
【数据范围与提示】
对于 20% 的数据，n, m ≤ 5。
对于 40% 的数据，n, m ≤ 50。
对于 70% 的数据，n, m ≤ 300。
对于 100% 的数据，1 ≤ n, m ≤ 1000。方格中整数的绝对值不超过 10000。

“这道题……”包涵宇和几名副队长浑身是汗，解不出题目啊！这个时候，他们想起来葛老师告诉他们，一定要冷静！
冷风呼呼地吹，冰霜慢慢地结，心里的火，终于燃烧！
剩余1分钟。包涵宇拍了一下大腿，忍下心提交了。
非静止画面……
大家倒吸一口寒风，结果缓慢地亮了出来：A.....
“AC了？”大家很怀疑，呼吸都屏住了。
几秒后，亮出的结果是：Accepted    100分
“耶！！！”欢呼声、欢笑声、雀跃声，响成一片。大家庆幸终于通过了入门测！！！
可是，队长包涵宇却高兴不起来。“哎！我没有带好这支队伍，让你们在一开始就受罪了……”“没事的，既然选你为队长，大家都相信你，就不要这么悲感。我们不是过去了吗？过去了就不要管那么多了。”
这支战队，终于进入了真正的挑战。可真正的挑战如此简单吗？恐怕不是吧……

曹灿阳在2021-07-21 16:07:00追加了内容

声明一下：我100%没有抄袭《酷町大陆》的内容，勿举报！