C. Standard Free2play——cf1238c（div2）（贪心）

阳光穿透心脏的1/2处 2023-06-06 03:54 6阅读 0赞

题目链接：https://codeforces.com/problemset/problem/1238/C

思路：  
每一个凸出层有两个状态， 一个状态是经过该层 ， 一个是不经过该层， 每个状态贪心取最小值。  
答案就是最后一层 两种状态的最小值。

#include<bits/stdc++.h>
    using namespace std;
    const int inf = 0x3f3f3f;
    const int maxn = 2e5+5;
    struct node
    { 
        int c;//层数
    
        int yes;// 经过该层 需要的魔法晶体
        int no;//不经过该层
    
    }p[maxn];
    int main()
    { 
        ios_base::sync_with_stdio(false);
        int T;
    
        cin>>T;
    
        while(T--)
        { 
            memset(p, inf, sizeof(p));// 初始化 晶体使用量为 inf
            p[0].no = p[0].yes = 0;// 初始化顶端 为 0
            int h, n;
            cin>>h>>n;
            for(int i = 0;i < n;i++)
            { 
                cin>>p[i].c;
            }
    
            for(int i = 1;i < n;i++)
            { 
                // 走该层
                p[i].yes = p[i-1].yes +1;// 从c+1层掉过来
                if(i-2>= 0 &&p[i-2].c -p[i].c >=2&&p[i-1].c == p[i].c+1)p[i].yes = min(p[i].yes, p[i-2].yes);// 从 c+2 层掉落过来
    
    
                //不走该层
                p[i].no = p[i-1].yes+2;//正常情况下 如果不走该层要使用两个 魔法晶体 （1个将该层隐藏， 另一个将c-1凸出 ）
    
                if(i+1< n &&p[i-1].c -2 >= p[i+1].c) // 不经过该层 c-1层本来就凸出 的情况
                { 
                    p[i].no = p[i-1].yes+1;
                }
                else if(p[i].c == 1)// 不经过该层 直接从第2层 落地的情况
                { 
                    p[i].no = p[i-1].yes;
                }
    
            }
            cout<<min(p[n-1].no, p[n-1].yes)<<endl;
    
        }
    
    
        return 0;
    }