总结：DP专题

题目解析：

T1：CF698A Vacations

题意： 每天只能休息、锻炼或比赛，不能连续两天做同样的事，求最少需要休息多少天。

思路： 用 dp[i][0/1/2]记录到第 i 天，选择休息、比赛或锻炼时的最大活动天数。 转移时，只要保证今天做的事不等于昨天做的事，并且今天具备做这件事的条件，就可以从昨天转移过来。最后用总天数减去最大活动天数，就是最少休息天数。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[110];
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int dp[105][3] = {0};
    if (a[1] == 0)
    {
        dp[1][0] = 0;
        dp[1][1] = -1e9; 
        dp[1][2] = -1e9;
    }
    else if (a[1] == 1)
    {
        dp[1][0] = 0;
        dp[1][1] = 1;
        dp[1][2] = -1e9;
    }
    else if (a[1] == 2)
    {
        dp[1][0] = 0;
        dp[1][1] = -1e9;
        dp[1][2] = 1;
    }
    else // a[1]==3
    {
        dp[1][0] = 0;
        dp[1][1] = 1;
        dp[1][2] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = max(max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
        dp[i][1] = -1e9;
        if (a[i] == 1 || a[i] == 3)
        {
            dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + 1;
        }
        dp[i][2] = -1e9;
        if (a[i] == 2 || a[i] == 3)
        {
            dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 1;
        }
    }
    int w = max(max(dp[n][0], dp[n][1]), dp[n][2]);
    cout << n - w << endl;
    return 0;
}

T2：CF489C Given Length and Sum of Digits

题意： 给定长度 m 和各位数字之和 s，求满足条件的最小和最大数。

思路： 贪心构造： 1.无解条件：如果 s == 0 且 m > 1（有前导零），或者 s > 9 * m（数字和太大装不下），直接输出 -1 -1。 2.最大数：从高位到低位，每次尽量填 9，填完为止。 3.最小数：从高位到低位，每次尽量填 0（首位填 1）。 注意：填当前数字 d 时，必须保证剩下的和 s - d 能被后面的位数装下（即 s - d <= 9 * 剩余位数）。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m, s;
    cin >> m >> s;
    if (s == 0 || s > 9 * m)
    {
        if (s == 0 && m == 1)
            cout << "0 0";
        else
            cout << "-1 -1";
        return 0;
    }
    string maxn, minn;
    int t;
    t = s;
    for (int i = 0; i < m; i++)
    {
        int c = min(9, t);
        maxn += (char)('0' + c);
        t -= c;
    }
    t = s;
    for (int i = 0; i < m; i++)
    {
        for (int d = (i == 0 ? 1 : 0); d <= 9; d++)//三元
        {
            if (t - d <= 9 * (m - i - 1))
            {
                minn += (char)('0' + d);
                t -= d;
                break;
            }
        }
    }
    cout << minn << " " << maxn;
    return 0;
}

T3：CF1881E Block Sequence

题意： 给定一个序列，要求删除最少的元素，使得剩下的序列能被完美划分为若干个区块，每个区块的第一个元素代表该区块的长度。

思路: 1.求最长合法子序列 删除最少的元素等价于保留最长的合法美丽序列。因此问题转化为，在原序列里，挑选出一个最长的子序列，使其能完美划分为若干个合法的区块。最终答案 = 总长度 n - 最长合法序列长度。 2.DP 用 dp[i] 表示:考虑到原序列的前 i 个元素，能组成的最长合法美丽序列的长度。 1.不选当前元素：dp[i] = dp[i - 1] 2.选当前元素作为新块头：假设当前元素为 x = a[i]，如果以它为开头，这个区块会占据 [i, i + x] 的位置。只要 i + x <= n（没越界），这个区块就是合法的。此时状态可以转移到 dp[i + x]，并且长度增加 x + 1（1个开头元素 + x个后续元素）, 即：dp[i + x] = max(dp[i + x], dp[i - 1] + x + 1)。 3. 遍历完所有状态后，找出 dp 数组中的最大值 mk（即能保留的最长合法长度）。 最终答案 = n - mk。

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int a[MAXN];
int dp[MAXN];
const int INF = -1e9;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        for(int i = 0; i <= n; i++)
        {
            dp[i] = INF;
        }
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            dp[i] = max(dp[i], dp[i - 1]);
            int x = a[i];
            int end = i + x;
            if (end <= n)
            {
                dp[end] = max(dp[end], dp[i - 1] + x + 1);
            }
        }
        int mk = 0;
        for (int i = 0; i <= n; i++)
        {
            mk = max(mk, dp[i]);
        }
        cout << n - mk << '\n';
    }
    return 0;
}

T4:CF766C Mahmoud and a Message

题意：给定一个字符串和每个字母允许出现的最大子串长度，求将字符串切分成若干合法子串的方案数、最长子串的最大长度、以及最少的子串个数。

思路： 从后往前枚举最后一个子串的起点，慢慢向前推导： 1.在从当前位置向前枚举子串起点的过程中，实时维护当前子串内所有字母的最大长度限制，一旦当前子串的实际长度超过了这个限制，说明该子串已不合法，直接停止向前枚举。 2.方案数统计： 如果当前枚举的子串合法，则将前缀部分的合法方案数累加到当前位置的总方案数中。 3.最长长度更新： 比较前缀部分的最长子串长度和当前枚举子串的长度，取最大值，用来更新当前位置的最长子串长度。 4.最少个数更新： 将前缀部分的最少子串个数加上当前的这1个子串，用来更新当前位置的最少子串个数。 5.输出

方案数：cnt[i] += cnt[j]。 最长长度：ml[i] = max(ml[i], max(ml[j], len))。 最少个数：ms[i] = min(ms[i], ms[j] + 1)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAXN = 1010;
int n;
string s;
int a[26];
long long cnt[MAXN];
int ml[MAXN];
int ms[MAXN];
int main()
{
    cin >> n >> s;
    for(int i = 0;i < 26;i++)
    {
        cin >> a[i];
    } 
    cnt[0] = 1;
    ms[0] = 0;
    ml[0] = 0;
    for(int i = 1;i <= n;i++)
    {
        cnt[i] = 0;
        ms[i] = INF;
        ml[i] = 0;
        int mi = INF;
        for(int j = i-1; j >= 0; j--)
        {
            int c = s[j] - 'a';
            mi = min(mi, a[c]);
            int len = i - j;
            if(len > mi) break; 
            cnt[i] = (cnt[i] + cnt[j]) % MOD;
            if(ms[j] + 1 < ms[i])
            {
                ms[i] = ms[j] + 1;
            }
            int now_max = max(ml[j], len);
            if(now_max > ml[i])
            {
                ml[i] = now_max;
            }
                
        }
    }
    cout << cnt[n] << "\n";
    cout << ml[n] << "\n";
    cout << ms[n] << "\n";
    return 0;
}

T5：CF1033C Permutation Game

题型：经典博弈论+DP 题意： 在一个由n个格子组成的棋盘上，棋子每次只能向数字更大的格子跳跃，且跳跃距离必须是当前格子数字的倍数，两方轮流操作，无法移动者输，求每个初始位置的必胜/必败状态。

思路： 1.定义 因为游戏规则要求只能向数字更大的格子移动，所以数字最大的格子一定是必败,所以我们可以从数字n到1逆序推导。用 win[i] 表示棋子在位置i时，当前玩家是否必胜。 2. 转移 对于当前数字为x的格子，玩家可以向两侧每隔x步进行跳跃,只要跳跃后的格子满足数字大于x，并且这个目标格子是必败，那么当前格子就是必胜，如果找到一条必胜路即可 break。 3. 确定必败 如果向左右跳跃，要么没有合法的目标格子，要么所有合法的目标格子都是必胜，说明当前玩家无论怎么走都会把必胜机会让给对方，那么当前格子就是必败。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> p(n + 1); 
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
        p[a[i]] = i;
    }
    vector<bool> win(n + 1, false); 
    for (int x = n; x >= 1;x--)
    {
        int i = p[x];
        bool ok = false;
        for (int j = i + x; j <= n; j += x)
        {
            if (a[j] > x)
            {
                if (!win[j])
                {
                    ok = true;
                    break;
                }
            }
        }
        if (!ok)
        {
            for (int j = i - x; j >= 1; j -= x)
            {
                if (a[j] > x)
                {
                    if (!win[j])
                    {
                        ok = true;
                        break;
                    }
                }
            }
        }
        win[i] = ok;
    }
    string ans;
    for (int i = 1; i <= n; ++i)
    {
        ans += win[i] ? 'A' : 'B';
    }
    cout << ans << endl;
    return 0;
}

T6:CF1036C Classy Numbers

题型：数位DP 题意： 统计区间 [L, R] 内，十进制表示中非零数字个数不超过 3 个的正整数（也就是高雅数）的个数。

思路： 1.前缀和转化 利用 count(r) - count(l - 1)，将求区间 [L, R] 的问题转化为求 [0, X] 范围内合法数字的个数。 2. 把目标数字拆成一位一位的数组，然后从高位到低位依次填数字。填的时候记录三个状态：当前填到了第几位、已经用了几个非零数字、当前是不是还卡着上限。 3.剪枝 如果非零数字用超了 3 个，直接停止往下搜；如果刚好填完所有位，说明找到了一个合法数字，返回 1。为了防止重复计算，把不受上限限制的状态结果存了起来，下次遇到直接拿来用。 4.状态转移 根据当前是否卡着上限，决定这一位最大能填几，然后从 0 到这个最大值挨个尝试，更新非零数字的个数和下一位的受限状态，继续往下搜，最后把所有合法情况的方案数加起来输出就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
long long dp[20][5];
long long dfs(int p, int cnt, int t)
{
    if(cnt > 3) return 0;
    if(p < 0) return 1;
    if(!t && dp[p][cnt] != -1) 
        return dp[p][cnt];
    int up = t ? a[p] : 9;
    long long res = 0;
    for(int d = 0; d <= up; d ++)
    {
        int nt = t && (d == a[p]);
        res += dfs(p - 1, cnt + (d != 0), nt);
    }
    if(!t) dp[p][cnt] = res;
    return res;
}
long long count(long long x)
{
    if(x < 0) return 0;
    a.clear();
    if(x == 0)  a.push_back(0);
    while(x > 0)
    {
        a.push_back(x % 10);
        x /= 10;
    }
    int p = a.size() - 1, cnt = 0, t = true;
    return dfs(p, cnt, t);
}
int main()
{
    int t;
    cin >> t;
    memset(dp, -1, sizeof dp);
    while(t --)
    {
        long long l, r;
        cin >> l >> r;
        cout << count(r) - count(l - 1) << endl;
    }
}