作业帮pascal题目瓶子涂色小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕.有一次他喝完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色.他觉得如果所有相邻的
来源：学生作业帮助网 编辑：作业帮 时间：2024/12/02 13:27:39
pascal题目瓶子涂色小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕.有一次他喝完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色.他觉得如果所有相邻的
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.
pascal题目瓶子涂色小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕.有一次他喝完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色.他觉得如果所有相邻的
【算法分析】无论第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种颜色所花费的最小代价,保证jk
最后输出的结果就是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