RGBStreet 刷房子【题解】

dp入门题之一

题目描述

今年，为了迎接亚运，广州的RGB街道的住户决定把他们的房子都刷成统一的红、绿、蓝三色之一。还规定相邻的两个房子不能刷成同样的颜色。第i个房子相邻的是第i-1和第i+1房子。
现在已经知道每个房子刷成三种颜色的花费，请你计算最少要花费多少才能完成这个任务。

输入输出格式

输入格式：

第一行为G，表示组数。下面G组每组格式为：
第一行，一个整数N；
第二至第n+1行，每行三个整数r，g，b。第i+1行的r，g，b表示第i个房子刷成红、绿、蓝色的分别花费。

输出格式：

每组数据一行，只一个整数，完成任务的最小花费。

输入样例：

1
3
1 100 100
100 100 100
1 100 100

输出样例：

102

虽然说我是一看到题目就一次 AC，但这也是一道对新手极不友好的题目。

首先解析题目，题目规定相邻的两个房子颜色不能相同，为了便与表达，我们将1表示红，2表示绿，3表示蓝，也就是说 colour[i] != colour[i+1]。由于限制，我们使用 dp 解题。

这里很多dp新手可能会只会设 f[i] 表示刷前 i 座房子的最小价值，设完后基本上就没有头绪了。正确的方法应该是使用设状态中的结尾状态法，设 f[i][j]表示刷前 i 座房子，且第 i 个房子刷颜色 j 的最小价值。如此设状态即可判断 colour[i] 是否等于 colour[i - 1]。

那么我们便很容易得到状态转移方程

f[i][j] = min{ f[i - 1][ 1…3 !=j ] }

如此一来，解题思路便得到了调整，最后便得出了 AC代码

#include<iostream>
#define For(a,b,c) for(int a=b;a<=c;a++)
//化简 for语句
using namespace std;
int t,n,a[35][4],f[35][4];
int main()
{
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	For(i,1,n)
    	    For(j,1,3)
    	        cin>>a[i][j];
    	f[1][1]=a[1][1];
    	f[1][2]=a[1][2];
    	f[1][3]=a[1][3];
    	//赋值初始化 f 数组
    	For(i,2,n)
    	    For(j,1,3)
    	        f[i][j]=0x7fffffff/3;
    	For(i,2,n)
    	{
    		For(j,1,3)
    		{
    			For(k,1,3)
    			    if(j!=k)
    			    {
    			    	f[i][j]=min(f[i][j],f[i-1][k]+a[i][j]);//状态转移
					}
			}
		}
		int minn=0x7fffffff/3;
		For(i,1,3)minn=min(minn,f[n][i]);//从三个答案状态中选最优
		cout<<minn<<endl;
	}
    return 0;
}

题目源于 GHOJ problem/537