返回信息流你要在一个nxm的格子图上涂色，你每次可以选择一个未涂色的格子涂上你开始选定的那种颜色。同时为了美观，我们要求你涂色的格子不能相邻，也就是说，不能有公共边，现在问你，在采取最优策略的情况下，你最多能涂多少个格子？
给定格子图的长n和宽m。请返回最多能涂的格子数目。
class Paint {
public:
int getMost(int n, int m) {
return (n * m + 1) >> 1;
}
};
这个结果是怎么得到的？ 求大神指点
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91223同步于 2016/9/24
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
涂色问题
ywg557
2016/9/24镜像同步1 回复
订阅后，新回复会通过你的通知中心匿名送达。
1 条回复
肯定是隔一格写最多，可反证法。
那么考虑mn为偶数奇数的各种情况:
m偶数 n偶数
1 3 5 7 9
2 4 6 8 10
1 3 5 7 9
2 4 6 8 10
mn/2
m奇数n偶
1 3 5 7 9
2 4 6 8 10
1 3 5 7 9
m * n/2
m偶n奇
1 3 5 7 9
2 4 6 8
m / 2 * n
m奇 n 奇
1 3 5 7 9 11
2 4 6 8 10
1 3 5 7 9 11
m+1 / 2 * n+1 /2 + m-1 / 2 +n-1 / 2
= mn + 1 / 2
所以可以统一写为mn + 1 / 2