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

浏览数：19 / 时间：2015年06月11日

题意：给你一块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 }