专题：动态规划1

这个暑假跟着灵神（0x3f）做每日一题，一周的周一到周五下午三点是有每日一题的，大概是cf上面1700或者1800难度，这周因为最近力扣出一些dp题目，灵神在cf上也找了一些比较相似的写。在我之前的博客文章中也有很多出自灵神的每日一题里面。

CF166E. Tetrahedron (1500)

题意

题目链接：Problem - 166E - Codeforces
给你一个n(1\leq n\leq 10^7)，你一开始在顶点D上，你需要去走n步并且回到D点，求这样的方案数是多少（对mod取模）。

思路

这一看就是DP题，不难看出A,B,C点对于D点是对称的，贡献是一样的，也就是所以我定义：

• dp[i][0] 表示走i步到达D点的方案数
• dp[i][1] 表示走i步到达A/B/C点的方案数

初始状态是dp[0][0] = 1，然后进行扫一遍，对于第i次：

• 首先看D 点是可以由其他三点转移过来，所以dp[i][0] = dp[i-1][1] * 3 % mod，乘以三是因为有三个点。
• 再来看A/B/C 点是可以由D点转移过来(dp[i-1][0])，也可以由其他两点转移过来（dp[i-1][1]*2）

代码

这个题比较简单

int dp[N][2];
inline void Case_Test()
{
    cin>>n;
    dp[0][0] = 1;
    for (int i=1;i<=n;i++)
    {
        dp[i][0] = dp[i-1][1]*3%mod;
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]*2)%mod;
    }
    cout<<dp[n][0];
}

CF1105C. Ayoub and Lost Array (1500)

题意

题目链接：Problem - 1105C - Codeforces

给你一个正整数n(1\leq n\leq 2\times 10^5)，还有l,r(1\leq l\leq r\leq 10^9)。求有多少个不同的长度为n的数组，数组元素值的范围为[l,r]，且数组元素之和为3的倍数。（对mod取模）

Input: 2 1 3
Output: 3

有三种可以符合的条件，分别是：[1,2],[2,1],[3,3]

思路

哪怕l,r的数再大，对我也没有关系，我只关心有多少个数对3取模为1,2,0，比如给你l=2,r=8，那么分成三类
- x[1]:对3取模为1的个数，\lbrace 4,7\rbrace。x[1] = 2
- x[2]:对3取模为2的个数，\lbrace 2,5,8\rbrace。x[2] = 3
- x[0]:对3取模为0的个数，\lbrace 3,6\rbrace。 x[0] = 2

我可以用一个二维数组来表示f[i][j]来表示选取了i个数后第j类（j=1,2,0）有多少个。

我处理好这些之后来看怎么进行dp:

因为这里的每一个数字都是可以打乱顺序的，没有顺序要求，也可以重复，比如样例的[1,2],[2,1]是两种答案，所以相当于我每次选取i类都有x[i]种。
举个例子：假如第2类有\lbrace 2,5,8 \rbrace，我要选取3个有多少种情况呢？我只需要每次都乘以x[2]也就是3^3=9种，不难想象，分别是[2,2,2],[2,2,5],[2,2,8],...,[8,8,5],[8,8,8]

基于以上，可以来写递推式了：
对于f[i][0]，可以从上一次0类再选一个0类，比在上一次的3的倍数那一类再选一个3的倍数进去。我也可以从上一次1类选一个2类进去，也就是在上一次对3取模为1的地方，选取一个对3取模为2的让其现在成为3的倍数。

其他情况都如此，也就是说对于一个f[i][j],我需要从上次的f[i-1][0],f[i-1][1],f[i-1][2]分别选出相应的类型让其变成j，其实也就是上一次的与选出的值相加对应j即可。

    f[1][0] = x[0], f[1][1] = x[1], f[1][2] = x[2];
    for (int i=2;i<=n;i++)
    {
        f[i][0] = (f[i-1][0]*x[0] + f[i-1][1]*x[2] + f[i-1][2]*x[1])%mod;
        f[i][1] = (f[i-1][0]*x[1] + f[i-1][1]*x[0] + f[i-1][2]*x[2])%mod;
        f[i][2] = (f[i-1][0]*x[2] + f[i-1][1]*x[1] + f[i-1][2]*x[0])%mod;
    }

这样的时间复杂度是O(n),这里值得一提的是，这个有O(logn)的时间复杂度的方法，也就是矩阵快速幂。

f = [x[0], x[1], x[2]]

x = [ [x[0], x[1], x[2]],
      [x[2], x[0], x[1]],
      [x[1], x[2], x[0]] ]

可以看出我由递推式可以的出这样的矩阵计算，乘以n-1次x矩阵。

代码

int l,r;
int f[N][3];
int x[3];
inline void Case_Test()
{
    cin>>n>>l>>r;
    m = r-l+1;
    x[0] = x[1] = x[2] = m/3;
    for (int i=l+(m/3)*3;i<=r;i++)
        x[i%3]++;
    f[1][0] = x[0], f[1][1] = x[1], f[1][2] = x[2];
    for (int i=2;i<=n;i++)
    {
        f[i][0] = (f[i-1][0]*x[0] + f[i-1][1]*x[2] + f[i-1][2]*x[1])%mod;
        f[i][1] = (f[i-1][0]*x[1] + f[i-1][1]*x[0] + f[i-1][2]*x[2])%mod;
        f[i][2] = (f[i-1][0]*x[2] + f[i-1][1]*x[1] + f[i-1][2]*x[0])%mod;
    }
    cout<<f[n][0];
}
/*可以用矩阵快速幂加速
f = [x[0], x[1], x[2]]

x = [ [x[0], x[1], x[2]],
      [x[2], x[0], x[1]],
      [x[1], x[2], x[0]] ]

qpow(n-1)次
*/

CF788A. Functions again (1600)

题意

题目链接：Problem - 788A - Codeforces
给你一个长度为n(1\leq n\leq 10^5)的数组a(-10^9\leq a_i\leq 10^9)，在满足1\leq l<r\leq n的前提下，输出f(l,r)的最大值，f的定义如下：

f(l,r)=\sum_{i=1}^{r-1}|a[i]-a[i+1]|\cdot (-i)^{i-l}

思路

• 对于奇偶性相同的l，(-1)^{i-l}的变化规律是相同的，也就是+,-,+,-,...。所以需要进行分开讨论。

• 其实求得就是|a[i]-a[i+1]|\cdot (-1)^{i-l}的最大子段和（贪心扫一遍去找）

• 正如第一条所说，只需要从对于奇偶性不同的来说，从1开始一遍，再从2开始一遍取Max即可。

代码

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    int flag = 1;//flag每次变化1,-1,1,-1,...
    int sum = 0;
    for (int i=1;i<n;i++)
    {
        if (i%2==1 && sum<0) 
            sum = 0;
        sum += flag*Abs(a[i]-a[i+1]);
        flag *= -1;
        ans = Max(ans, sum);
    }
    flag = 1;
    sum = 0;
    for (int i=2;i<n;i++)//从2开始再来一遍
    {
        if (i%2==0 && sum<0) 
            sum = 0;
        sum += flag*Abs(a[i]-a[i+1]);
        flag *= -1;
        ans = Max(ans, sum);
    }
    cout<<ans;
}

CF1084C. The Fair Nut and String (1500)

题意

题目连接：Problem - 1084C - Codeforces
给你一个字符串s，长度不超过10^5，只有小写字母组成。求出满足如下条件s下标序列的p的个数

1. 对于每一个i，都有s_{p_i}='a'
2. 满足从小到大的关系p_i<p_{i+1}
3. 相邻两个序列下标之间需要至少有一个'b'，也就是s_{p_i}和s_{p_{i+1}}之间。

思路

用f[i]表示s的前i个字母的合法序列个数。
- 当s[i]!='a'时候，就继承f[i]=f[i-1]
- 当s[i]=='a'的时候，f[i]=f[i-1]+f[last['b']]+1，这里的1表示新加自己，然后last['b']表示的是上一次b出现的下标。

答案就是f[n]了。

至于第二个式子怎么来的，可以这么理解：第一个f[i-1]表示不选，f[last['b']表示选择当前的，当前的不与前一个字母有关，而是与前一个b有关。

代码

vector<int> v;
int f[N];
inline void Case_Test()
{
    cin>>s;
    n = s.length();
    s = " " + s;
    v.push_back(0);
    for (int i=1;i<=n;i++)
        if (s[i]=='b') v.push_back(i);
    v.push_back(n+1);
    x = 0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='a')
            f[i] = (f[i-1] + f[v[x]] + 1) %mod;
        else 
        {
            if (s[i]=='b')
                x++;
            f[i] = f[i-1];
        }
    }
    cout<<f[n];
}

这里的v和x是找上一个b出现的位置。

也可以简化成一维的

inline void Case_Test()
{
    cin>>s;
    n = s.size();
    for (int i=0;i<n;i++)
        if (s[i]=='a')
            ans = (ans + pre + 1) % mod;
        else if (s[i]=='b')
            pre = ans;
    cout<<ans;
}

至此，灵神这周的每日一题就写在这里的。下周继续！