【lightoj1047】Neighbor House

怼烎@ 2022-07-17 01:46 129阅读 0赞

1047 - Neighbor House

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1047" style="color:rgb(202,0,0); text-decoration:none" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt="" style="border:none; max-width:100%"></a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1047&amp;language=english&amp;type=pdf" style="color:rgb(202,0,0); text-decoration:none" rel="nofollow">PDF (English)</a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1047" style="color:rgb(202,0,0); text-decoration:none" rel="nofollow">Statistics</a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1047" style="color:rgb(202,0,0); text-decoration:none" rel="nofollow">Forum</a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit:&nbsp;<span style="color:rgb(180,95,4)">0.5 second(s)</span></td> 
   <td>Memory Limit:&nbsp;<span style="color:rgb(180,95,4)">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

The people of Mohammadpur have decided to paint each oftheir houses red, green, or blue. They've also decided that no two neighboringhouses will be painted the same color. The neighbors of house**i** arehouses **i-1** and **i+1**. The first and last houses are not neighbors.

You will be given the information of houses. Each house willcontain three integers**"R G B"** (quotes for clarity only),where **R, G** and **B** are the costs of painting the correspondinghouse red, green, and blue, respectively. Return the minimal total costrequired to perform the work.

# Input #

Input starts with an integer **T (≤ 100)**,denoting the number of test cases.

Each case begins with a blank line and an integer**n (1≤ n ≤ 20)** denoting the number of houses. Each of the next **n**lines will contain 3 integers **"R G B"**. These integers will liein the range**\[1, 1000\]**.

# Output #

For each case of input you have to print the case number andthe minimal cost.

<table> 
 <tbody> 
  <tr> 
   <td> <h1 style="margin:0px; padding:0px"><a style="color:rgb(202,0,0)" rel="nofollow"></a><span style="font-size:14px">Sample Input</span></h1> </td> 
   <td> <h1 style="margin:0px; padding:0px"><a style="color:rgb(202,0,0)" rel="nofollow"></a><span style="font-size:14px">Output for Sample Input</span></h1> </td> 
  </tr> 
  <tr> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">2</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">&nbsp;</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">4</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">13 23 12</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">77 36 64</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">44 89 76</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">31 78 45</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">&nbsp;</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">3</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">26 40 83</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">49 60 57</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">13 89 99</span></p> </td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">Case 1: 137</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:14px">Case 2: 96</span></p> </td> 
  </tr> 
 </tbody> 
</table>

题目链接：[http://lightoj.com/volume\_showproblem.php?problem=1047][http_lightoj.com_volume_showproblem.php_problem_1047]

dp题目，看来还是对dp理解不够深啊，没看出来用dp。其实看出来dp后算是一道dp的水题。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #define INF 0x3f3f3f3f
    #include<algorithm>
    using namespace std;
    int map[22][5],dp[22][5];
    int main() {
    	int T,p=0;
    	scanf("%d",&T);
    	while(T--) {
    	//	printf("\n");                 //加上格式错误。
    		int n;
    		memset(dp,0,sizeof(dp));
    		scanf("%d",&n);
    		for(int i=1; i<=n; i++) {
    			for(int j=0; j<3; j++) {
    				scanf("%d",&map[i][j]);
    			}
    		}
    		int ans=0,tab=4;
    		dp[1][0]=map[1][0];
    		dp[1][1]=map[1][1];
    		dp[1][2]=map[1][2];
    		for(int i=2; i<=n; i++) {
    			dp[i][0]=min(dp[i-1][1]+map[i][0],dp[i-1][2]+map[i][0]);
    			dp[i][1]=min(dp[i-1][0]+map[i][1],dp[i-1][2]+map[i][1]);
    			dp[i][2]=min(dp[i-1][0]+map[i][2],dp[i-1][1]+map[i][2]);
    		}
    		ans=min(min(dp[n][0],dp[n][1]),dp[n][2]);
    		printf("Case %d: %d\n",++p,ans);
    	}
    	return 0;
    }

[http_lightoj.com_volume_showproblem.php_problem_1047]: http://lightoj.com/volume_showproblem.php?problem=1047