D - Neighbor House

dp

题目大意

有n个房子，每个房子都可以染红绿蓝三种颜色，并且给出了每个房子染每种颜色费用，相邻房子不能同色，求染完房子的最小费用

解题思路

简单的DP。dp[i][j]就是第i个房子染第j个颜色后的总费用。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 30;
int mat[N][3];
int dp[N][3];
int n, cas = 1;
void init() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            scanf("%d", &mat[i][j]);
}
void solve() {
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = mat[0][0];
    dp[0][1] = mat[0][1];
    dp[0][2] = mat[0][2];
    for (int i = 1; i < n; i++) 
        for (int j = 0; j < 3; j++) 
            for (int k = 0; k < 3; k++)
                if (j != k) dp[i][j] = min(dp[i][j], dp[i - 1][k] + mat[i][j]);
    printf("Case %d: %d\n", cas++, min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]));
}
int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}