目录
一、题目
二、代码
一、题目
不要二__牛客网
二、代码
采用贪心算法的思想来做,开始全置为1,1代表放入蛋糕。
从左向右从上到下遍历棋盘开始依此放蛋糕,然后将该块蛋糕上下左右欧几里得距离为2的点全部标记为0,表示该点不能再放入蛋糕,如果下一步扫到的0,则跳过该点,如果扫到1,则sum++,继续把周围距离为2的点标记为0。
#include <iostream>
#include <vector>
using namespace std;int main() {int W,H;cin>>W>>H;vector<vector<int>>isCake(W,vector<int>(H,1));//开始假设都能放蛋糕int sum=0;for(int i=0;i<W;i++){for(int j=0;j<H;j++){if(isCake[i][j]==1){++sum;if(i+2<W)isCake[i+2][j] = 0;if(j+2<H)isCake[i][j+2] = 0;}}}cout<<sum;return 0;}