1 条题解

  • 0
    @ 2025-8-10 16:27:28

    状态定义:

    a[i]a[i] :第 ii 天看书时,前 ii 天的最少看电视天数。

    b[i]b[i] :第 ii 天打球时,前 ii 天的最少看电视天数。

    c[i]c[i] :第 ii 天看电视时,前 ii 天的最少看电视天数。

    状态转移:

    如果第 ii 天看电视,前一天可以是任何活动状态。

    如果第 ii 天看书,前一天不能是看书。

    如果第 ii 天打球,前一天不能是打球。

    初始化:

    00 天(初始状态)的看电视天数为 00 ,看书和打球的天数为 ∞(表示不可行)。

    #include<bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    typedef pair<LL, LL> PII;
    
    #define x first
    #define y second
    
    const int N = 2e5 + 10, M = 30;
    
    int a[N], b[N], c[N]; // 看书,打球,电视
    int n;
    
    void solve() 
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i ++) a[i] = b[i] = c[i] = 1e9;
        for(int i = 1; i <= n; i ++)
        {
            int x;
            cin >> x;
            if(x == 1 || x == 3)
                b[i] = min(c[i - 1], a[i - 1]);
            if(x == 2 || x == 3)
                a[i] = min(b[i - 1], c[i - 1]);
            c[i] = min({a[i - 1], b[i - 1], c[i - 1]}) + 1;
        }
        cout << min({a[n], b[n], c[n]});
    }            
    
    int main()
    {
        int t = 1;
        // cin >> t;
        while(t --)
            solve();
    }
    
    • 1

    信息

    ID
    496
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    3
    上传者