Question

pascal题目:数字游戏

第3题 数字游戏
提交文件：game.exe
输入文件：game.in
输出文件：game.out
题目描述：
小W发明了一个游戏，他在黑板上写出了一行数字a1，a2，a3，……，an，然后给你M个回合的机会，每回合你可以从中选择一个数字擦去它，接着剩下来的每个数字ai都要递减一个值bi,即a1减掉b1,a2减掉b2,….。如此重复M个回合，所有你擦去的数字之和就是你所得的分数。
小W和他的好朋友小Y玩了这个游戏，可是他发现，对于每个给出的an和bn序列，小Y的得分总比他高，所以他就很不服气。于是他想让你帮他算算，对于每个an和bn序列，可以得到的最大得分是多少。这样他就知道有没有可能超过小Y的得分。

输入格式(game.in):
输入文件的第一行是一个整数n（1<=n<=2000），表示数字个数；第二行一个整数m（1<=m<=n），表示回合数，接下来一行有n个不超过10000的正整数，a1，a2，a3，……，an表示原始序列，最后一行有n个不超过500的正整数，b1，b2，b3，……，bn，表示每回合每个数字递减的值。

输出格式(game.out):
输出文件只有一个整数，表示最大的可能得分。

输入样例：
3
3
10 20 30
4 5 6

输出样例：
47

Answer 1

var
a, b: array[1..500] of integer;
f: array[0..500, 0..500] of longint;
n, m, i, j: integer;
function max(a, b: longint): longint;
begin
if a < b then
max := b
else
max := a;
end;
procedure qsort(l, r: longint);
var
i, j, m, t: longint;
begin
i := l;
j := r;
m := b[(i + j) div 2];
repeat
while b[i] > m do
Inc(i);
while b[j] < m do
Dec(j);
if i <= j then
begin
t := a[i];
a[i] := a[j];
a[j] := t;
t := b[i];
b[i] := b[j];
b[j] := t;
Inc(i);
Dec(j);
end;
until i > j;
if i < r then
qsort(i, r);
if l < j then
qsort(l, j);
end;
begin
assign(input,'game.in');
reset(input);
assign(output,'game.out');
rewrite(output);
fillchar(f, sizeof(f), 0);
readln(n, m);
for i := 1 to n do
Read(a[i]);
readln;
for i := 1 to n do
Read(b[i]);
readln;
qsort(1, n);
for i := 1 to n do
for j := 1 to m do
f[i, j] := max(f[i - 1, j], f[i - 1, j - 1] + a[i] - b[i] * (j - 1));
writeln(f[n, m]);
readln;
close(input);
close(output);
end.

Answer 2

也许是分拍板把

Answer 3

==做出来了告你

Answer 4

32

Answer 5

42