$$开发区规划$$

---

题目

小王是D市主管经济的副市长，由于经济发展的需要，要在D市组建一个高新技术开发区，经过研究，规划局在D市的东部划出了一块土地作为开发区选址。这块土地是一块矩形平原，小王准备在上面修建一些建筑。为了规划方便，他将矩形划分成NM格。棘手的是，这块土地有些历史文化遗址散布在某些格子内，这些历史文化遗址是万万不能拆除的，否则将激起民愤，小王深知这一点，因此，他的新建筑在选址时要避开这些格子。
　　假设新的建筑物有P种规格，每种建筑物都是正方形的，占地为TiTi格 (1<=i<=P)。小王想知道对于每种规格的建筑，有多少种不同的合适选址方案（一种合适的选址方案指的是在该建筑所占的正方形区域内不存在有历史文化遗址的格子）。现在请你来当小王的秘书 帮他完成这个光荣而艰巨的任务。

---

输入

从文件$d.in$读入数据，输入文件第一行包含三个数，分别代表$N,M,P$ $(1<=N,M<=2000,1<=P<=1000)$ 随后的$n$行，每行有$m$个$0$或$1$（$1$表示该格为空地，$0$表示该格有历史文化遗址）。接下来的$P$行每行有一个整数$Ti$

输出

结果输出到文件$d.out$中，共有$P$行，每行一个整数，第$i$行的数代表边长为$Ti$的建筑物选址方案数。

---

输入样例

4 4 2 1011 1111 1110 1110 2 3

输出样例

5 1

---

解题思路

这题我们可以根据样例来处理
例如:
可以根据其中每个数字代表以该格为右下角，最多可以达成边长为多少的正方形
然后统计，每种边长都可以由比它大的边长的格子达成

1011 1112 1220 1230

程序如下

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;int n, m, p, k, Max;int a[10001][1001], f[10001][1001], t[10001], b[10001][1001];char x[10001];int main() {scanf("%d%d%d", &n, &m, &p);for(int i = 1; i <= n; ++i){scanf("%s",&x);for(int j = 1; j <= m; ++j)a[i][j] = x[j - 1] - '0';for(int j = 1; j <= m; ++j)if(a[i][j] != 0) f[i][j] = f[i][j - 1] + 1;//统计正方形数量}for(int j = 1; j <= m; ++j)for(int i = 1; i <= n; ++i)if(a[i][j] != 0) b[i][j] = b[i - 1][j] + 1;-for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)if(a[i][j] != 0){a[i][j] = min(min(a[i - 1][j - 1] + 1, f[i][j]), b[i][j]);//求最优解t[a[i][j]]++;}Max = max(n , m);for(int i = Max - 1; i >= 1; --i)t[i] += t[i + 1];for(int i = 1; i <= p; ++i){scanf("%d", &k);printf("%d\n",t[k]);}return 0; }

总结

以上是生活随笔为你收集整理的【09年特长生第四题】开发区规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。