noip 2009 普及组 第四题怎么做

来源：百度知道 编辑：UC知道 时间：2024/07/07 12:25:10
就是道路游戏那题
DP的状态和转移方程最好写上
标程加注释
感激不禁
P的程序我看不懂 希望是C或C++的

var
x: array[1..1000, 1..1000] of longint;
v: array[1..1000] of longint;
f: array[0..1000] of longint;
n, m, p, i, j, iBuyRobot, k, r: longint;

begin
readln(n, m, p);
for i := 1 to n do
for j := 1 to m do
read(x[i, j]);
for i := 1 to n do
read(v[i]);

for j := 1 to m do
// 依次计算每个单位时间最多能收集的金币数
begin
for i := 1 to n do
// 试验机器人收集金币的终点，实质上是试验从哪个厂买机器人
// 因为买机器人需要金币，所以倒着运行以方便把购买所需资金放在后面进行比较
begin
r := 0;
iBuyRobot := i + 1;
for k := j downto j-p+1 do
// 试验设置机器人行走次数
begin
if k = 0 then
// 退行到最开始即停止
break;
dec(iBuyRobot);
if iBuyRobot = 0 then
iBuyRobot := n;
r := r + x[iBuyRobot, k]; // 机器人在这段路上收集的金币