包含哪些题目

\huge B \cdot C \cdot D \cdot E \cdot F
集训题目链接

B

飞翔 跳跃的牛

总之，有这样的转移方程(P[i]代表这颗药的效力)：
DP(n,isodd)=\begin{cases} \max \begin{cases} DP(n-1,isodd) \cr DP(n-1,!isodd)+\begin{cases} P[n]&isodd \cr -P[n] &!isodd \end{cases}\end{cases}&n>0 \cr \begin{cases} P[0]&isodd \cr 0 &!isodd \end{cases} &n=0\end{cases}
具体实现是这样的

int oddDP(int n,bool isodd)
{
    int odd = isodd ? 0 : 1;
    if (n==0)
    {
        return isodd?potions[n]:0;
    }
    else
    {
        if (mem_DP[n][odd]!=-1)
        {
            return mem_DP[n][odd];
        }
        else
        {
            return mem_DP[n][odd] = max(oddDP(n - 1, isodd), oddDP(n-1,!isodd) + (isodd ? potions[n] : -potions[n]));
        }
    }
}

c

脸 接苹果的牛 顿

如果用apple[i][j]代表i时刻，第j颗树上掉苹果的数量。有转移方程：
DP(i,w)= \begin{cases} 0&i<0\cr \sum_{a=0}^{i}{apple[a][0]}&i 0 \wedge i > w \end{cases}
以下为代码

int DP(int t, int w)//t是阶段，w是已经用了的转换
{
    if (t < 0)
    {
        return 0;
    }
    else
    {
        if (w<=0)
        {
            int r = 0;
            for (size_t i = 0; i <= t; i++)
            {
                r += apples[i][0];
            }
            return r;
        }
        if (mem_DP[t][w] != -1)
        {
            return mem_DP[t][w];
        }
        else
        {
            return mem_DP[t][w] = max(DP(t - 1, w), DP(t - 1, w - 1)) + apples[t][w % 2];
        }
    }
}

D

破坏谷仓

无向图找环；有就“NONE”，没有就遍历每个节点，如果它的所有子节点的深度够低就直接输出。

E

回文串的创造

问一个给定字符串要添加几个字符可以变成回文串。
简单来说，字符串长度减去它与其逆序串的最长公共子字串的长度。
至于LCS，请看此处。

F

矩阵求最大子阵

首先，当然可以试试暴力法。用n^2枚举左上角，用n^2枚举右下角，再用n^2求和。
\Huge \sout{小学生} n^6 \sout {真是太棒了！}
明显暴力过头了。来改进一下。
设原矩阵为n[i][j]有
sum[i][j]=\sum_{a=0}^{i}\sum_{b=0}^{j}{n[a][b]}
则可证
\sum_{a=i}^{i^{\star}}\sum_{b=j}^{j^{\star}}{n[a][b]}=sum[i^{\star}][j^{\star}]-sum[i][j^{\star}]-sum[i^{\star}][j]+sum[i][j]
这样子，通过n^2的预处理，可以实现o(1)的求和。

但是还不够好

考虑一维情形，最大子段和是有n的算法的，而其如上优化过的暴力方法是n^2的。
方案呼之欲出了。
枚举0 \le i \le j,把第i行到第j行压缩成一维。用最大子段和的算法处理。求总的最大值。