Hust oj 1861 猥琐宅男——koko(DP)

唔。。从前有个小胖子叫koko（QAQ。。。）很喜欢吃香蕉，茄子和黄瓜（唔。。好奇怪的癖好。。。），而且每天都必须且只能吃一个而且相邻两天不能吃一样的水果~（为什么必须吃一个？因为不吃会受不了，为什么只能吃一个？因为吃多了会受不了~）唔。由于这三种水果（水果！？）灰常可怕，可以吸收天地之间离散的邪恶值，所以呢koko希望你能帮他设计一种方案使得koko在n天内吃这三种水果获得的邪恶值最小~。

输入以T开头，代表有T组样例

每组样例第一行有一个整数n(1<=n<=40000),代表koko希望你帮他规划n天的饮食方案，接下来n行每行有三个数字，X, Q, H分别代表在这一天吃香蕉，茄子，和黄瓜会获得的邪恶值(1<=X, Q, H<=1000)

对于每一组样例输出可以获得的最小邪恶值

2

4

13 23 12

77 36 64

44 89 76

31 78 45

3

26 40 83

49 60 57

13 89 99

Case 1: 137

Case 2: 96

水DP

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int Maxn = 40005;
int t,n;
int dp[Maxn][3];
int a[Maxn][3];
int cnt = 0;
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);}memset(dp,0,sizeof(dp));dp[0][0] = a[0][0];dp[0][1] = a[0][1];dp[0][2] = a[0][2];for(int i=1;i<n;i++){dp[i][0] = a[i][0] + min(dp[i-1][1],dp[i-1][2]);dp[i][1] = a[i][1] + min(dp[i-1][0],dp[i-1][2]);dp[i][2] = a[i][2] + min(dp[i-1][0],dp[i-1][1]);}printf("Case %d: %d\n",++cnt,min(dp[n-1][0],min(dp[n-1][1],dp[n-1][2])));}return 0;
}