本文共 1275 字，大约阅读时间需要 4 分钟。

题目地址

题目大意

给一个nm的图，分成11的多个格子。每个格子有两种操作，第一种是种树，第二种是施肥，如果施肥的话，其相邻的上下左右格子收益都会变成二倍。问你最多能收获多少苹果。

解题思路

首先我们看1 * 1 的图，最多收获为1, 1*2最多收获两个，1 * 3最多收获4个，由此类推得到一行的收获为1, 2, 4, 6, 8…
通过观察我们发现只有每两棵树之间施肥才能得到最大收益。并且并不需要固定树的位置，比如1 * 3, 可以是树肥树，也可以是肥树肥。
那么对于一列来说同样是每两棵树之间施肥才能得到最大收益，并且根据第一行来确定第二行，比如第一行第一个位置如果选择种树，那么第二行第一个位置必须施肥。这样通过贪心的方法就得到了最大收益。

AC代码

#include <iostream>#include <cstring>using namespace std;int Map[110][110];int main(){
   	int t;		cin >> t;		while (t--)	{
   		int n, m, flag = 0, sum = 0;				cin >> n >> m;				for (int i=0; i<n; i++)			for (int j=0; j<m; j++)				Map[i][j] = 1;				for (int i=0; i<n; i++)		{
   			for (int j=0; j<m; j++)			{
   				if (i%2 == 0)				{
   					if (j%2 != 0)					{
   						Map[i][j] = 0;												if (i > 0)							Map[i-1][j] *= 2;						if (j + 1 < m)							Map[i][j+1] *= 2;						if (i + 1 < n)							Map[i+1][j] *= 2;						if (j-1>=0)							Map[i][j-1] *= 2;					}				}				else				{
   					if (j%2 == 0)					{
   						Map[i][j] = 0;												if (i > 0)							Map[i-1][j] *= 2;						if (j + 1 < m)							Map[i][j+1] *= 2;						if (i + 1 < n)							Map[i+1][j] *= 2;						if (j-1>=0)							Map[i][j-1] *= 2;					}				}			}		}				for (int i=0; i<n; i++)			for (int j=0; j<m; j++)				sum += Map[i][j];					cout << sum << endl;	}		return 0;}