hdu ---(4517)小小明系列故事——游戏的烦恼(Dp)
小小明系列故事——游戏的烦恼
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 841 Accepted Submission(s): 296
Problem Description
小小明最近在玩一款游戏，它由n*m大小的矩阵构成，矩阵上会随机产生一些黑色的点，这些点它们可能会连在一起也可能会分开，这些点的个数没有限制，但 是每个1*1方格中最多只可能有一个黑点产生。游戏要求玩家以最短的时间用x*y的小矩阵覆盖这个大矩阵，覆盖的要求有以下2点： 1. x*y大小的小矩阵内必须有x*y个黑点。 2. 多个小矩阵可以重叠，但是每个小矩阵放置的位置必须是独一无二的，即不同的小矩阵内的黑点不能完全相同。例如1*2的矩阵可以横着放，也可以竖着放，这两种方法是不同的，即使它们可能共用黑点。 小小明是个粗心的孩子，他尝试了很多遍都无法将所有的符合要求的小矩阵找到，聪明的你，能不能告诉烦恼中的小小明这个大矩阵里有多少个满足要求的小矩阵呢？
Input
题目有多组测试数据（不多于100个）； 每组测试数据的第一行包含2个正整数n和m，然后第二行是x和y（n，m，x，y的意思如题），接下来n行，每行m个字符，其中’ * ’表示黑点，’ . ’表示空白。 n和m为0则结束输入。 [Technical Specification] 0 < n, m <= 2000 0 < x, y <= 1000
Output
请计算并输出一共有多少个满足要求的小矩阵，每组输出占一行。
Sample Input
2 3 1 2
**.
.**
0 0
Sample Output
3
Source
刚开始进行了个普通的匹配，O(∩_∩)O~，就知道会TLE，╮(╯▽╰)╭，就是这么无奈呀！
贴一下自己丑陋的代码吧..
代码：
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 using namespace std;
5 const int maxn=2005;
6 char map[maxn][maxn];
7 int n,m;
8 bool match(int posx,int posy,int x,int y)
9 {
10 int i,j;
11 if(posx+x>n||posx<0||posy+y>m||posy<0)
12 return 0;
13 for( i=posx; i<posx+x ; i++ ){
14 for( j=posy ; j<posy+y ; j++ ) {
15 if(map[i][j]!='*')return false;
16 }
17 }
18 return true;
19 }
20
21 int work(int x,int y)
22 {
23 int i,j,cnt=0;
24 for(i=0;i<n;i++){
25 for(j=0;j<m;j++){
26 if(match(i,j,x,y)) cnt++;
27 if(match(i,j,y,x)) cnt++;
28 }
29 }
30 return cnt;
31 }
32 int main()
33 {
34 int x,y,i;
35 while(scanf("%d%d",&n,&m)!=EOF,n+m!=0)
36 {
37 scanf("%d%d",&x,&y);
38 for(i=0;i<n;i++)
39 scanf("%s",map[i]);
40 printf("%d\n",work(x,y));
41 }
42 return 0;
43 }然后统计了一下，dp...简单的dp
代码： 不过依旧还是很挫，写到了680ms....
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 using namespace std;
5 const int maxn=2005;
6 char map[maxn][maxn];
7 int dp[maxn][maxn];
8 int n,m;
9 void init()
10 {
11 int i,j,cnt=0;
12 memset(dp,0,sizeof(dp));
13 for(i=1;i<=n;i++) {
14 for(j=1;j<=m;j++) {
15 if(map[i][j-1]=='*')cnt++;
16 dp[i][j]=cnt+dp[i-1][j];
17 }
18 cnt=0;
19 }
20 }
21 int work(int x,int y){
22 int i,j,cnt=0;
23 for(i=1;i+x<=n;i++){
24 for(j=1;j+y<=m;j++){
25 int tem=dp[i+x][j+y]-dp[i-1][j+y]-dp[i+x][j-1]+dp[i-1][j-1];
26 if(tem==((x+1)*(y+1)))cnt++;
27 }
28 }
29 return cnt;
30 }
31 int main()
32 {
33 int x,y,i;
34 while(scanf("%d%d",&n,&m),n+m!=0)
35 {
36 scanf("%d%d",&x,&y);
37 x--,y--;
38 for(i=1;i<=n;i++)
39 scanf("%s",map[i]);
40 init();
41 if(x==y) printf("%d\n",work(x,y));
42 else printf("%d\n",work(x,y)+work(y,x));
43
44 }
45 return 0;
46 }