pascal题目

pascal题目

【算法分析】无论第i个瓶子涂什么颜色（但一定不能与第i-1个瓶子的颜色相同），都与涂完前i-1个瓶子所需的最小代价无关，所以这题很显然需要使用动态规划算法
用f[i,j]表示第i个瓶子涂第j种颜色所花费的最小代价，从而得到状态转移方程：
f[i,j]:=min{f[i,j],f[i-1,k]+g[i,j]} //f[i-1,k]表示第i-1个瓶子涂第k种颜色所花费的最小代价，保证j<>k
最后输出的结果就是f[n,1],f[n,2],f[n,3]中的最小值
算法时间复杂度O(9*n)
（还有建议LZ如果以后决定往计算机竞赛这方面发展得话趁早学些C++的基本知识，毕竟目前网络上的解题报告大部分都是用C++语言的、、、）
【参考程序】
var n,i,j,k:longint;
f,g:array[0..100000,1..3]of longint;
function min(x,y:longint):longint;
begin
if x else exit(y);
end;
begin
readln(n);
for i:=1 to 3 do
for j:=1 to n do
read(g[j,i]);
fillchar(f,sizeof(f),100);
for k:=1 to 3 do f[0,k]:=0;
for i:=1 to n do
for j:=1 to 3 do
for k:=1 to 3 do
if j<>k then
f[i,j]:=min(f[i,j],f[i-1,k]+g[i,j]);
writeln(min(min(f[n,1],f[n,2]),f[n,3]));
end.
【评测结果】找不到评测网站╮(╯▽╰)╭、、、