Question

pascal题目

瓶子涂色

题目描述
小猪上小学的时候，一度对颜色非常感兴趣，虽然他的美术非常糟糕。

有一次他喝完n瓶饮料把透明的瓶子排成一排，想把这些饮料瓶子都涂上颜色。他觉得如果所有相邻的两个瓶子颜色都不一样的话会比较有趣。

他现在只有红色(Red)、绿色(Green)和蓝色(Blue)这三种颜料。由于瓶子的大小和表面材质不同，在不同的瓶子上涂不同的颜色需要的花费都不一样。小猪统计了一下，把第i个瓶子染成红色需要Ri元钱，染成绿色需要Gi元钱，染成蓝色需要Bi元钱。

现在请你帮他计算出要使相邻两个瓶子的颜色都不一样，他至少需要多少花费。
输入
第一行只有一个整数n，表示共有n只瓶子。

第二行有n个正整数（以一个空格分隔）,第i个数Ri表示把第i个瓶子染成红色需要Ri元钱。

第三行有n个正整数（以一个空格分隔）,第i个数Gi表示把第i个瓶子染成绿色需要Gi元钱。

第四行有n个正整数（以一个空格分隔）,第i个数Bi表示把第i个瓶子染成蓝色需要Bi元钱。

输出
仅有一行，该行只有一个整数，表示最小花费。
样例输入
5
1 3 1 2 2
1 2 3 4 3
4 2 1 5 3
样例输出
9
提示

【数据规模】

30%的数据中，1≤n≤10；

70%的数据中，1≤n≤30；

100%的数据中，1≤n≤100000，1≤Ri, Gi, Bi≤100。

Answer 1

【算法分析】无论第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<y then exit(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.
【评测结果】找不到评测网站╮(╯▽╰)╭、、、