Codeforces Round #363 (Div. 2) C. Vacations 贪心+dp

Source

Codeforces Round #363 (Div. 2)

My Solution

贪心+dp

//!从前往后， 前面的决定后面的， dp的思想， 前面处理完的时候前面部分是最优的了

如果第一位是 3， 第二位任意，直到出现一个1或者2

后面的如果是0还是0，如果是3就要相应的转化成1 或者 2

if(val[0] == 0) ans++;

对于 i = 1 ~ n-1

if(val[i] == 1 && val[i-1] == 1){
ans++;
val[i] = 0;

}
else if(val[i] == 2 && val[i-1] == 2){
ans++;
val[i] = 0;
}
else if(val[i] == 0) ans++;
else if(val[i] == 3){
if(val[i-1] == 1) val[i] = 2;
else if(val[i-1] == 2) val[i] = 1;
//!如果 val[i-1] == 0, 则任意， 对后面没有影响的 无论后面是 0 1 2 3
}

复杂度 O(n)

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e2 + 8;

int val[maxn];

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 3;
    while(T--){
    #endif // LOCAL

    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &val[i]);
    }
    //!从前往后， 前面的决定后面的， dp的思想， 前面处理完的时候前面部分是最优的了
    //!贪心+dp
    if(val[0] == 0) ans++;
    for(int i = 1; i < n; i++){
        if(val[i] == 1 && val[i-1] == 1){
            ans++;
            val[i] = 0;
        }
        else if(val[i] == 2 && val[i-1] == 2){
            ans++;
            val[i] = 0;
        }
        else if(val[i] == 0) ans++;
        else if(val[i] == 3){
            if(val[i-1] == 1) val[i] = 2;
            else if(val[i-1] == 2) val[i] = 1;
            //!如果 val[i-1] == 0, 则任意， 对后面没有影响的 无论后面是 0 1 2 3
        }

    }
    printf("%d", ans);
    #ifdef LOCAL
    printf("n");
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx