pascal题目瓶子涂色小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕.有一次他喝完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色.他觉得如果所有相邻的
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/11 18:07:29
![pascal题目瓶子涂色小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕.有一次他喝完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色.他觉得如果所有相邻的](/uploads/image/z/955092-12-2.jpg?t=pascal%E9%A2%98%E7%9B%AE%E7%93%B6%E5%AD%90%E6%B6%82%E8%89%B2%E5%B0%8F%E7%8C%AA%E4%B8%8A%E5%B0%8F%E5%AD%A6%E7%9A%84%E6%97%B6%E5%80%99%2C%E4%B8%80%E5%BA%A6%E5%AF%B9%E9%A2%9C%E8%89%B2%E9%9D%9E%E5%B8%B8%E6%84%9F%E5%85%B4%E8%B6%A3%2C%E8%99%BD%E7%84%B6%E4%BB%96%E7%9A%84%E7%BE%8E%E6%9C%AF%E9%9D%9E%E5%B8%B8%E7%B3%9F%E7%B3%95%26%2361516%3B.%E6%9C%89%E4%B8%80%E6%AC%A1%E4%BB%96%E5%96%9D%E5%AE%8Cn%E7%93%B6%E9%A5%AE%E6%96%99%E6%8A%8A%E9%80%8F%E6%98%8E%E7%9A%84%E7%93%B6%E5%AD%90%E6%8E%92%E6%88%90%E4%B8%80%E6%8E%92%2C%E6%83%B3%E6%8A%8A%E8%BF%99%E4%BA%9B%E9%A5%AE%E6%96%99%E7%93%B6%E5%AD%90%E9%83%BD%E6%B6%82%E4%B8%8A%E9%A2%9C%E8%89%B2.%E4%BB%96%E8%A7%89%E5%BE%97%E5%A6%82%E6%9E%9C%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E7%9A%84)
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