首页 > 代码库 > 2014多校第六场 1005 || HDU 4925 Apple Tree

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

2024-07-16 08:44:33   217人阅读

题目链接

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

 


联系
我们