Submission #792819

#	Time	Username	Problem	Language	Result	Execution time	Memory
792819		vjudge1	Lamps (JOI19_lamps)	C++14	4 / 100	24 ms	4224 KiB

lamp

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = 1e6, NS = 2000 ;
int n ;
bool flag ;
char a[N + 1], b[N + 2] ;
int dist[N + 1], dp[NS + 1][NS + 1] ;
map<int, int> pref, sum ;
void bfs()
{
    int num = 0 ;
    deque<int> d ;
    for(int i = 0 ; i < n ; i++)
        if(a[i] == '1')
            num ^= (1 << i) ;
    d.push_back(num) ;
    dist[num] = 1 ;
    while(d.size())
    {
        int now = d[0] ;
        d.pop_front() ;
        for(int i = 0 ; i < n ; i++)
            for(int j = i ; j < n ; j++)
            {
                int num1 = now, num2 = now, num3 = now ;
                for(int q = i ; q <= j ; q++)
                {
                    num1 |= (1 << q) ;
                    if(now & (1 << q))num2 ^= (1 << q) ;
                    num3 ^= (1 << q) ;
                }
                if(!dist[num1])
                {
                    d.push_back(num1) ;
                    dist[num1] = dist[now] + 1 ;
                }
                if(!dist[num2])
                {
                    d.push_back(num2) ;
                    dist[num2] = dist[now] + 1 ;
                }
                if(!dist[num3])
                {
                    d.push_back(num3) ;
                    dist[num3] = dist[now] + 1 ;
                }
            }
    }
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> a[i] ;
        if(a[i] == '1')
            flag = 1 ;
    }
    for(int i = 0 ; i < n ; i++)
        cin >> b[i] ;
    if(!flag)
    {
        int ans = 0 ;
        b[n] = '0' ;
        for(int i = 0 ; i < n ; i++)
            if(b[i] == '1' && b[i + 1] == '0')
                ans++ ;
        cout << ans ;
        return 0 ;
    }
    for(int i = 0 ; i < n ; i++)
    {
        pref[i] = pref[i - 1] + (a[i] != b[i]) ;
        sum[i] = sum[i - 1] + (a[i] - '0') ;
    }
    for(int i = 0 ; i < n ; i++)
        for(int j = i + 1 ; j < n ; j++)
            dp[i][j] = 1e9 ;
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            dp[i][i]++ ;
    for(int ln = 2 ; ln <= n ; ln++)
        for(int j = 0 ; j <= n - ln ; j++)
        {
            int cnt1 = 1, cnt0 = 1 ;
            for(int q = j ; q <= j + ln - 1 ; q++)
            {
                if(q > j && b[q] == '0' && b[q - 1] == '1')
                    cnt1++ ;
                if(q > j && b[q] == '1' && b[q - 1] == '0')
                    cnt0++ ;
                if(q == j + ln - 1)
                    continue ;
                dp[j][j + ln - 1] = min(dp[j][j + ln - 1], dp[j][q] + dp[q + 1][j + ln - 1]) ;
            }
            if(b[j + ln - 1] == '1')
                cnt1++ ;
            if(b[j + ln - 1] == '0')
                cnt0++ ;
            if(pref[j + ln - 1] - pref[j - 1] == ln)
                dp[j][j + ln - 1] = 1 ;
            dp[j][j + ln - 1] = min(dp[j][j + ln - 1], cnt1) ;
            dp[j][j + ln - 1] = min(dp[j][j + ln - 1], cnt0) ;
        }
    cout << dp[0][n - 1] ;
    return 0 ;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49