首页 > 其他 > 详细

lightOJ 1047 Neighbor House (DP)

时间:2015-03-03 09:59:21      阅读:356      评论:0      收藏:0      [点我收藏+]

题目链接:lightOJ 1047 Neighbor House

题意:有N做房子,每个房子涂3种颜色各有一个花费,相邻的房子颜色不能一样,给N个房子涂颜色,问完成这个任务的最小花费。

dp[i][j] 表示涂到第i个房子涂j颜色的最小花费。

状态转移方程:dp[i][k]=min(dp[i][k],dp[i-1][j]+p[i].c[k]);



AC代码:


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int inf=9999999999;
struct node{
	int c[5];
};
struct node p[30];
int dp[30][10];//前i个邻居颜色j的最小话费
//0 1 2

int main()
{
	int cas=1;
	int t,n,i,j,k;
	scanf("%d",&t);
	while(t--){
		memset(dp,0,sizeof dp);
		scanf("%d",&n);
		for(i=0;i<n;i++){
			for(j=0;j<3;j++){
				scanf("%d",&p[i].c[j]);
			}
		}
		for(i=0;i<3;i++){
			dp[0][i]=p[0].c[i];
		}
		for(i=1;i<n;i++){
			for(j=0;j<3;j++){
				if(!dp[i-1][j]) continue;
				for(k=0;k<3;k++){
					if(k==j)  continue;
					if(!dp[i][k]) dp[i][k]=dp[i-1][j]+p[i].c[k];
					else dp[i][k]=min(dp[i][k],dp[i-1][j]+p[i].c[k]);
				}
			}
		}
		int ans=inf;
		for(i=0;i<3;i++){
			if(!dp[n-1][i]) continue;
			ans=min(ans,dp[n-1][i]);
		}
		printf("Case %d: %d\n",cas++,ans);
	}
	return 0;
}
/*
3
3
5 2 3
1 2 2
2 1 9


3
1 2 1
1 2 4
7 11 9

*/


lightOJ 1047 Neighbor House (DP)

原文:http://blog.csdn.net/u012377575/article/details/44023913

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!