Sơn nhà - LCOJ: Luyện Code Online Judge

HOUSE - Sơn nhà

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Trên một con đường có ~n~ tòa nhà. Mỗi tòa nhà được sơn bằng một màu Đỏ, Vàng, Xanh, hoặc Tím. Người ta muốn sơn lại một số tòa nhà (bằng một trong các màu Đỏ, Vàng, Xanh, Tím) sao cho không có hai tòa nhà liên tiếp có cùng màu sơn. Tìm số nhà cần sơn lại ít nhất.

Input

Dòng đầu tiên chứa số nguyên dương ~n\ (1 ≤ n ≤ 2500)~;
Dòng tiếp theo chứa một xâu kí tự có độ dài ~n~, mỗi kí tự đại diện cho một tòa nhà. Mỗi kí tự có thể là ~D, V, X~, hoặc ~T~, lần lượt đại diện cho một ngôi nhà được sơn màu Đỏ, Vàng, Xanh, hoặc Tím.

Output

In ra số lượng nhà cần sơn lại ít nhất.

Sample

Input #1

2
TX

Output #1

Input #2

3
TXV

Output #2

Input #3

14
VVXDDTXVTXDVXV

Output #3

Input #4

17
DDTVVTDVVVTVVTDVV

Output #4

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

#include <iostream>
#include <string>
using namespace std;

int main() 
{
    int n;
    string s;
    cin >> n >> s;

    int cnt = 0;
    for (int i = 1; i < n; ++i) 
    {
        if (s[i] == s[i - 1]) {
            cnt++;
            i++;
        }
    }

    cout << cnt;
    return 0;
}

0

npg2011 đã bình luận lúc 26, Tháng 11, 2025, 12:16

include<bits/stdc++.h>

using namespace std; const long long N=1e6+6; long long a[N]; int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); long long n; cin>>n; cin.ignore(); string s; cin>>s; long long dem=0; long long d=1; for(long long i=0;i<s.size()-1;i++) { if(s[i]==s[i+1]) { dem++; } else { if(dem>0) { a[d]=dem+1; d++; dem=0; } } } if(dem>0) { a[d]=dem+1; d++; } d--; long long tg=0; for(long long i=1;i<=d;i++) { tg+=a[i]/2; } cout<<tg; return 0; } // tham khảo cách mình nha các ae

include <bits/stdc++.h>

using namespace std;

int main() { int n; string s; cin >> n >> s;

string colors = "DVXT";
const int INF = 1e9;
vector<vector<int>> dp(n, vector<int>(4, INF));

for (int c = 0; c < 4; c++) {
    dp[0][c] = (s[0] != colors[c]);
}

for (int i = 1; i < n; i++) {
    for (int c = 0; c < 4; c++) {
        for (int prev = 0; prev < 4; prev++) {
            if (c == prev) continue;
            dp[i][c] = min(dp[i][c], dp[i-1][prev] + (s[i] != colors[c]));
        }
    }
}

cout << *min_element(dp[n-1].begin(), dp[n-1].end());
return 0;

}

-1

oqtn75 đã bình luận lúc 23, Tháng 8, 2025, 23:41

ai chi tui xin code di

0

FluffyKhoi đã bình luận lúc 22, Tháng 7, 2025, 14:49

Bài này cứ vòng lặp thôi nha ae