P146SUMA spoj PTIT - Chuyển đổi

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P146SUMA/

Nội dung bài viết

1. Đề bài P146SUMA spoj
2. Gợi ý P146SUMA spoj PTIT
3. Code tham khảo P146SUMA spoj PTIT

1. Đề bài P146SUMA spoj

Tèo đang chơi một trò chới với dãy số. Dãy số của Tèo chỉ gồm các số 0 hoặc 1. Tèo đang cần chuyển đổi một đoạn của dãy số để sao cho số lượng số 1 là nhiều nhất.

Chuyển đổi một đoạn là thay các số a[i] trong đoạn đó bằng số x, với x = 1 – a[i].

Các bạn giúp Tèo chọn đoạn để chuyển đổi nhé.

Input

Dòng đầu tiên là số nguyên n (1 <=n <= 100).

Dòng thứ hai là dãy số của Tèo.

Output

Số lượng số 1 nhiều nhất mà Tèo có thể có được.

Example

Test 1:

Input:

1 0 0 1 0

Output:

Test 2:

Input:

1 0 0 1

Output:

2. Gợi ý P146SUMA spoj PTIT

Với n<=100 bài này có thể dễ dàng áp dụng duyệt O(n^3).

3. Code tham khảo P146SUMA spoj PTIT

const   fi='';
        nmax=100;
type    data=longint;
var
        f:text;
        A:array[1..nmax+2] of byte;
        n:data;
        dem:data;
procedure docfile;
var     i:data;
begin
        dem:=0;
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                begin
                        read(f,a[i]);
                        if a[i]=1 then
                                inc(dem);
                end;
end;

procedure xuli;
var     i,j,k,tmp,res:data;
begin
        res:=0;
        for i:=1 to n do
                for j:=i to n do
                        begin
                                tmp:=dem;
                                for k:=i to j do
                                        if a[k]=1 then
                                                dec(tmp)
                                        else
                                                inc(tmp);
                                if tmp>res then
                                        res:=tmp;
                        end;
        writeln(res);
end;

begin
        docfile;
        xuli;
end.

const fi='';

nmax=100;

type data=longint;

var

f:text;

A:array[1..nmax+2] of byte;

n:data;

dem:data;

procedure docfile;

var i:data;

begin

dem:=0;

assign(f,fi); reset(f);

readln(f,n);

for i:=1 to n do

begin

read(f,a[i]);

if a[i]=1 then

inc(dem);

end;

procedure xuli;

var i,j,k,tmp,res:data;

begin

res:=0;

for i:=1 to n do

for j:=i to n do

begin

tmp:=dem;

for k:=i to j do

if a[k]=1 then

dec(tmp)

else

inc(tmp);

if tmp>res then

res:=tmp;

end;

writeln(res);

end;

begin

docfile;

xuli;

end.

P146SUMA spoj PTIT – Chuyển đổi

1. Đề bài P146SUMA spoj

Input

Output

Example

2. Gợi ý P146SUMA spoj PTIT

3. Code tham khảo P146SUMA spoj PTIT

Bài viết liên quan

2 thoughts on “P146SUMA spoj PTIT – Chuyển đổi”

Trả lời Hủy