Решение задачи "Игра с переворачиванием " с Codeforces

Без пояснения   Просмотров: 23


Яхубу стало скучно и он придумал игру, в которую надо играть на бумаге.

Яхуб выписывает n целых чисел a1, a2, ..., an. Каждое из этих целых чисел может быть равно 0 или 1. Ему разрешено выполнить ровно одно действие: выбрать два индекса i и j (1 ≤ i ≤ j ≤ n) и перевернуть все значения ak, позиции которых находятся на отрезке [i, j] (то есть i ≤ k ≤ j). Перевернуть значение x, значит выполнить операцию x = 1 - x.

Цель игры — получить максимальное количество единиц после ровно одного хода. Напишите программу, которая решает маленькую игру Яхуба.

Код

#include <bits/stdc++.h>
using namespace std;
int sum(string s)
{
    int k = 0;
    for(int i = 0;i < s.size(); ++i){
        if(s[i] - 48)
            ++k;
    }
    return k;
}
 
int main()
{
    int n, tt;
    string s;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> tt;
        s+=tt+48;
    }
    int k = sum(s);
    if(k == s.size()){
        cout << k - 1;
        return 0;
    }
    int ii, jj;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '0'){
            ii = i;
            break;
        }
    }
    for(int i = s.size() - 1; i >= 0; --i){
        if(s[i] == '0'){
            jj = i;
            break;
        }
    }
    // cout << ii << " " << jj << endl;
    string s1 = s.substr(ii, jj - ii + 1);
    s1+="10";
 
 
    vector<int> v0;
    vector<int> v1;
    vector<string> arr;
    int pos = 0;
    for(int i = 0; i < s1.size(); ++i){
        if(s1[i] == '0' && s1[i + 1] == '1')
            for(int j = i + 1; j < s1.size(); ++j)
                if(s1[j] == '0'){
                   arr.push_back(s1.substr(pos, j - pos));
                   pos = j;
                   break;
                }
    }
    string ss = arr[arr.size() - 1];
    while(ss[ss.size() - 1] == '1'){
        ss.pop_back();
    }
    arr[arr.size() - 1] = ss;
    //cout << endl;
//    for(auto i: arr)
//        cout << i << endl;
 
 
//    cout << endl;
    for(auto i: arr){
        int kk = sum(i);
        v1.push_back(kk);
        v0.push_back(i.size() - kk);
    }
//    cout <<  endl;
//    for(auto i: v1)
//        cout << i << " ";
//    cout <<  endl;
//    for(auto i: v0)
//        cout << i << " ";
 
    int res = 0;
    // cout << endl;
    for(int i = 0; i < arr.size(); ++i){
        for(int j = i; j < arr.size(); ++j){
            string temp;
            int q1 = 0, q0 = 0;
            for(int h = i; h < j; ++h){
                temp+=arr[h];
                q1 += v1[h];
                q0 += v0[h];
            }
            q0+=v0[j];
            res = max(k + q0 - q1, res);
        }
    }
    cout << res;
    return 0;
}

/*
код на питон
n=int(input())
a=list(map(int,input().split()))
print(max(sum(a)-2*sum(a[i:j])+j-i for i in range(n)for j in range(i+1,n+1)))
*/

         


<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор Photo" /> Автор:


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться