02/10/2018, 14:39
P146SUMA spoj PTIT – Chuyển đổi
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P146SUMA/ 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ố ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P146SUMA/
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:
5
1 0 0 1 0
Output:
4
Test 2:
Input:
4
1 0 0 1
Output:
4
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | 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. |
