用文言 AC Luogu P1115 最大子段和

ZnO34 · 2020-01-14 16:11:56 · 题解

注意，此篇题解写于2019年，当时luogu还能通过文言语言提交代码。不要再问这是什么语言了。

吾有一術。名之曰「最大子段和」。欲行是術，必先得「文言lang」。

~~散裝文言警告~~

Luogu 支持「文言」以來，未見其題解多见【通今「現」】。予閒來無事，乃尋題于 Luogu。遂得「最大子段和」一題，乃AC之以「文言」。

提交記錄

有感，遂作此篇以記之。

解題思路

在座各位都已清楚此題思路，不多贅述。欲解此題，必行動態規劃之術。設 dp[i] 為強制以 a[i] 結尾的最大子段和。顯然，有選與不選之擇。

如 dp[i-1]<0 則無需用 a[i] “接上”前面的一段，乃“自立門戶”，dp[i]=a[i] 。否則，用 a[i] 接上前面一段,得 dp[i]=dp[i-1] + a[i] 。

考慮到 dp[i] 只會由 dp[i-1] 轉移得來，可以拋掉數組不要。就有了一樓題解的實現方式。

文言的实现

来到这篇题解的主题内容，我也不用散装文言和繁体字来恶心各位大佬了。接下来我会分几个简单的步骤来用文言实现这个简单的问题。

输入

由于这一段是重点所以太长以至于可能发不上来，有兴趣的大佬们欢迎移步博客。传送门

前置工作

luogu A+B Problem 拉到最下面就有文言版的实现。因为“文言尚菜”，所以“无对象之操作”，我们需要外接 JavaScript 来从 stdin 得到输入。如下：

施「require('fs').readFileSync」於「「/dev/stdin」」。名之曰「數據」。
施「(buf => buf.toString().trim())」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.split(' '))」於「數據」。昔之「數據」者。今其是矣。
注曰。「「文言尚菜，無對象之操作，故需 JavaScript 之语法」」。

夫「數據」之一。取一以施「parseInt」。名之曰「甲」。
夫「數據」之二。取一以施「parseInt」。名之曰「乙」。

加「甲」以「乙」。書之。

其中最前面三行是开头所必须（第四行是注释）。它起到了暂时“外挂”JavaScript 的作用。然而，我们发现第三行中

施「(s => s.split(' '))」於「數據」。昔之「數據」者。今其是矣。

仅仅起到了将“空格”分割开来的效果。要 ac 这一题，首先要输入一个项数 n，接着是一个回车。用例程的这一句不能正常获得“数据”数组，怎么办呢？不多啰嗦，上代码。

施「(s => s.replace('\n',' '))」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.replace('\r',''))」於「數據」。昔之「數據」者。今其是矣。

这一段外挂 JavaScript 的代码放在 split 之前。它将所有的 \n 替换成了空格，将所有的 \r 都去掉了（在 linux 下似乎并不必要但是如果不加 luogu 的在线 IDE 会出错），这样就解决了这个问题。完整代码如下：

施「require('fs').readFileSync」於「「/dev/stdin」」。名之曰「數據」。
施「(buf => buf.toString().trim())」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.replace('\n',' '))」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.replace('\r',''))」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.split(' '))」於「數據」。昔之「數據」者。今其是矣。

可以得到一个名为“数据數據”的数组，里面存的是每一个输入的数。

单次读入

得到这个数组后，每一次我们想要读入一个数，可以这样读入：

夫「數據」之n。取一以施「parseInt」。名之曰「xx」。

其中 n 是输入文件的第 n 个数，而 xx 是用来存的变量名。举例：

夫「數據」之一。取一以施「parseInt」。名之曰「甲」。
夫「數據」之二。取一以施「parseInt」。名之曰「乙」。

那如果我想要读入一个已经被定义的变量呢？

有两种办法，一是声明一个临时变量，然后把这个变量的值赋给已经被定义的变量。

吾有一數。名之曰「已有變量」。
夫「數據」之三。取一以施「parseInt」。名之曰「臨時變量」。
昔之「已有變量」者。今「臨時變量」是矣。

另有一更简单的写法：

夫「數據」之二。取一以施「parseInt」。昔之「已有變量」者。今其是矣。

循环读入

因为这一题由于 dp[i] 由 dp[i-1] 转移得来，我们可以将一个数组压缩成一个变量，不需要数组。~~其实只是我不会读数组……~~观察读入一个变量的语句，比较难求的是这个 n 。我们可以维护一个「項數」变量来读入。看代码：

夫「數據」之一。取一以施「parseInt」。名之曰「項數」。
吾有一數。曰二。名之曰「第幾項」。
為是「項數」遍。
    夫「數據」之「第幾項」。取一以施「parseInt」。名之曰「本項」。
    加一於「第幾項」。昔之「第幾項」者。今其是矣。
云云。

不难理解，用一个「第幾項」维护了输入的索引。

对于数组的读入和一些其他内容~~因为不会~~暂时不在这里说了。有时间再补上吧。

控制流程

我们需要了解“为是项数遍”。它的作用相当一个从一到「項數」的 for 循环。从 GitHub 中的“为是百遍”得来——Github传送门。

在这一题中，我们用到的有：

為是「項數」遍。
    省略
   若「和」小於零者。
       昔之「和」者。今零是矣。
   云云。
    省略
云云。

在这段代码之中，先是一个执行项数次的循环，里面嵌套了一个条件判断语句。以云云作为结束的大括号。

非常好理解，套用即可，不多赘述。

赋值和运算

把加减乘除用「於」「以」连接起来就完事了。举一个例子即可：

加一於「第幾項」。昔之「第幾項」者。今其是矣。

执行“加一於「第幾項」”后，编译器会把它执行后的结果存下来，等待一个指代。我们利用其一字来获取它的值。

而文言中标准的赋值语句格式为：

昔之xxx者。今yyy是矣。

作用为将 yyy 的值赋给 xxx。相当于 xxx=yyy。

最终实现代码

将上文所述结合起来，我们得到了一篇 AC 代码：

施「require('fs').readFileSync」於「「/dev/stdin」」。名之曰「數據」。
施「(buf => buf.toString().trim())」於「數據」。昔之「數據」者。今其是矣。

施「(s => s.replace('\n',' '))」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.replace('\r',''))」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.split(' '))」於「數據」。昔之「數據」者。今其是矣。

注曰。「「文言尚菜，無對象之操作，故需 JavaScript 之语法」」。

夫「數據」之一。取一以施「parseInt」。名之曰「項數」。
減「項數」以一。昔之「項數」者。今其是矣。
吾有一數。曰三。名之曰「第幾項」。
夫「數據」之二。取一以施「parseInt」。名之曰「最大值」。
吾有一數。名之曰「和」。 昔之「和」者。今「最大值」是矣。
為是「項數」遍。
    夫「數據」之「第幾項」。取一以施「parseInt」。名之曰「本項」。
    若「和」小於零者。
        昔之「和」者。今零是矣。
    云云。
    加「本項」於「和」。 昔之「和」者。 今其是矣。
    若「和」大於「最大值」者。
        昔之「最大值」者。今「和」是矣。
    云云。
    加一於「第幾項」。昔之「第幾項」者。今其是矣。
云云。
夫「最大值」。書之。

完结撒花！！！