02/10/2018, 13:57
LINEGAME spoj – VOI09 Trò chơi với băng số
Nguồn đề bài: http://vn.spoj.com/problems/LINEGAME/ 1. Đề bài LINEGAME spoj Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi ...
Nguồn đề bài: http://vn.spoj.com/problems/LINEGAME/
1. Đề bài LINEGAME spoj
Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương ai, i = 1, 2, …, n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i1, i2, …, ik. Khi đó điểm số mà người chơi đạt được sẽ là:
- ai1 – ai2 + … + (-1)k-1aik
Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương n ( n ≤ 106 ) là số lượng ô của băng số;
- Dòng thứ hai chứa n số nguyên dương a1, a2, …, an ( ai ≤ 104, i = 1, 2, …, n ) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.
Kết quả
- Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.
Ví dụ
| Dữ liệu | Kết quả |
|---|---|
| 7 4 9 2 4 1 3 7 | 17 |
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.
==============================
bài này sử dụng QHĐ:
2. code tham khảo LINEGAME spoj pascal , c++:
uses math;
const fi=';
nmax=1000000;
type data=longint;
var
n:data;
a:array[1..nmax] of word;
cong,tru:array[1..nmax] of int64;
f:text;
procedure docfile;
var i:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
close(f);
end;
procedure bpa;
var i:data;
begin
cong[1]:=a[1];
tru[1]:=0;
for i:=2 to n do
begin
cong[i]:=max(tru[i-1]+a[i],cong[i-1]);
tru[i]:=max(cong[i-1]-a[i],tru[i-1]);
end;
writeln(max(cong[n],tru[n]));
end;
begin
docfile;
bpa;
//readln;
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 | uses math; const fi='; nmax=1000000; type data=longint; var n:data; a:array[1..nmax] of word; cong,tru:array[1..nmax] of int64; f:text; procedure docfile; var i:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); close(f); end; procedure bpa; var i:data; begin cong[1]:=a[1]; tru[1]:=0; for i:=2 to n do begin cong[i]:=max(tru[i-1]+a[i],cong[i-1]); tru[i]:=max(cong[i-1]-a[i],tru[i-1]); end; writeln(max(cong[n],tru[n])); end; begin docfile; bpa; //readln; end. |
#include<cstdio>
using namespace std;
typedef long long int ll;
int main()
{
int n,tg;
ll max=0,m1=0,m2=0,m3;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&tg);
m3=m1;
if(m1<m2+tg) m1=m2+tg;
if(m2<m3-tg) m2=m3-tg;
}
if(m1>max) max=m1;
if(m2>max) max=m2;
printf("%lld",max);
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include<cstdio> using namespace std; typedef long long int ll; int main() { int n,tg; ll max=0,m1=0,m2=0,m3; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&tg); m3=m1; if(m1<m2+tg) m1=m2+tg; if(m2<m3-tg) m2=m3-tg; } if(m1>max) max=m1; if(m2>max) max=m2; printf("%lld",max); } |
