2014多校第六场 1005 || HDU 4925 Apple Tree

题目链接

题意 : 给你一块n×m的矩阵,每一个格子可以施肥或者是种苹果,种一颗苹果可以得到一个苹果,但是如果你在一个格子上施了肥,那么所有与该格子相邻(指上下左右)的有苹果树的地方最后得到的苹果是两倍,如果(i,j)有一颗苹果树,(i-1,j)与(i,j+1)施了肥,那么苹果应该是1的两倍2,2的两倍4,最后是4个苹果,问你怎么安排苹果和施肥的格子使最后得到的苹果最多。

思路 : 画了图就可以看出来,苹果和苹果,肥与肥之间不要相邻就好了,所有的苹果之间都有施肥,所有施肥的格子都被苹果隔开了才能得到最多的苹果。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #define LL long long
 5 
 6 using namespace std ;
 7 
 8 int mp[110][110] ;
 9 
10 int main()
11 {
12     int T ,n,m;
13     cin >> T ;
14     while(T--)
15     {
16         cin >> n >> m ;
17         if(n == 1 && m == 1)
18         {
19             printf("1\n") ;
20             continue ;
21         }
22         memset(mp,0,sizeof(mp)) ;
23         for(int i = 1 ; i <= n ; i++)
24         {
25             if(i % 2)
26             {
27                 for(int j = 1 ; j <= m ; j += 2)
28                     mp[i][j] = 1 ;
29             }
30             else
31             {
32                 for(int j = 2 ; j <= m ; j += 2)
33                     mp[i][j] = 1 ;
34             }
35         }
36         LL ans = 0,cnt;
37         for(int i = 1 ; i <= n ; i++)
38         {
39             for(int j = 1 ; j <= m ; j++)
40             {
41                 cnt = 0 ;
42                 if(mp[i][j]) continue ;
43                 if(i-1 >= 1 && mp[i-1][j]) cnt ++ ;
44                 if(i+1 <= n && mp[i+1][j]) cnt ++ ;
45                 if(j-1 >= 1 && mp[i][j-1]) cnt ++ ;
46                 if(j+1 <= m && mp[i][j+1]) cnt ++ ;
47                 ans += 1LL << cnt ;
48             }
49         }
50         printf("%I64d\n",ans) ;
51     }
52     return 0 ;
53 }
View Code

 

2014多校第六场 1005 || HDU 4925 Apple Tree,,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。