[Codeforces][Round #EDU111][Div.2] B : Maximum Cost Deletion (C++)

https://codeforces.com/contest/1550/problem/B

Problem - B - Codeforces

 

 

[난이도] Div.2
[유형] Greedy

[풀이]
길이 n의 string s가 주어질때 총 지워지는 길이는 n이므로
a*l + b에서 a*l은 결국 a,b 값에 무관하게 정답에 포함되게 됩니다.
Deletion이 일어나는 횟수만큼 b가 추가되게 되므로
b가 음수인지, 양수인지에 따라 deletion 횟수를 최소화 할지, 최대화 해야할지를 정해야합니다.

b가 양수이면
deletion이 최대한 많이 일어나야 하므로 모든 원소를 1씩 지우게 되면
b*n만큼이 정답에 더해지게 됩니다.
결국 a*n+b*n이 b가 양수일때는 cost를 높이는 최적의 값입니다.

b가 음수이면
deletion이 최대한 적게 일어나야 하므로 지울 수 있는 안쪽의 문자열부터 직접 지워봐서 몇번 지워지는지 확인해봅니다.

"000111000111000" -> "000000111000" -> "000000000" -> ""

예를 들어 위와같이 3번 지우면 deletion을 최소로 지울 수 있습니다.

(tutorial을 보면 직접 해보지 않고도 수식으로 간단하게 답을 구하는 풀이가 있습니다.)

 

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,n,a,b;
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> n >> a >> b >> s;
        int ans = n*a;
        if(b>0){
            ans+=b*n;
        }else if(b<0){

            int l=0;
            while(1){
                bool ok=1;
                int sidx=-1,eidx=-1;
                for(int i=1;i<s.size();i++){
                    if(s[i]!=s[i-1]){
                        sidx=i;
                        eidx=i;
                        ok=0;
                        for(int j=i+1;j<s.size()&&s[j]==s[i];j++){
                            eidx=j;
                        }
                        break;
                    }
                }
                if(ok) {
                    if(!s.empty()) l++;
                    break;
                }
                l++;
                s.erase(sidx,eidx-sidx+1);
            }

            ans+=l*b;
        }
        printf("%d\n",ans);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU111-Div.2/B.cpp