1047 - Neighbor House（简单线性DP）

题目大意：

给你n个房子，要求把房子染成R,G,B三种的一种颜色，

要求相邻的颜色不能一样。

dp[第i个房子][第j种颜色] 转移一下就行了。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

int dp[MAXN][];///dp[第n个房子][房子的颜色]

int R[MAXN], G[MAXN], B[MAXN];

int main()

{

    int T, cas = , n;

    scanf("%d", &T);

    while(T --)

    {

        memset(dp, , sizeof(dp));

        scanf("%d", &n);

        for(int i=; i<=n; i++)

            scanf("%d %d %d", &R[i], &G[i], &B[i]);

        for(int i=; i<=n; i++)

        for(int j=; j<; j++)

        {

            dp[i][] = min(dp[i-][], dp[i-][]) + R[i];

            dp[i][] = min(dp[i-][], dp[i-][]) + G[i];

            dp[i][] = min(dp[i-][], dp[i-][]) + B[i];

        }

        int ans = min(min(dp[n][], dp[n][]),dp[n][]);

        printf("Case %d: %d\n",cas ++, ans );

    }

    return ;

}