洛谷 P1002 过河卒

题目传送门

解题思路:

f[i][j]表示到(i,j)的方案数,则f[i][j] = f[i-1][j] + f[i][j-1];

代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 long long n,m,n1,m1,f[21][21];
 7 bool a[101][101];
 8 
 9 int main() {
10     scanf("%lld%lld%lld%lld",&n,&m,&n1,&m1);
11     a[n1][m1] = a[n1-2][m1-1] = a[n1-1][m1-2] = a[n1-2][m1+1] = a[n1-1][m1+2] = a[n1+1][m1-2] = a[n1+2][m1-1] = a[n1+1][m1+2] = a[n1+2][m1+1] = 1;
12     f[0][0] = 1;
13     for(int i = 1;i <= m; i++)
14         if(a[0][i])
15             break;
16         else
17             f[0][i] = f[0][i-1];
18     for(int i = 1;i <= n; i++)
19         if(a[i][0])
20             break;
21         else
22             f[i][0] = f[i-1][0];
23     for(int i = 1;i <= n; i++)
24         for(int j = 1;j <= m; j++)
25             if(!a[i][j])
26                 f[i][j] = f[i-1][j] + f[i][j-1];        
27     printf("%lld",f[n][m]);
28     return 0;
29 }

朴素做法

看了题解后,发现可以优化空间,状态再压一维.

f[j] = f[j] + f[j-1]; (j表示列)

咋来的呢? 再每一个f[j]更新前,其实原来储存的是上一行的第j列的答案.举个例子:我已经枚举到第3行了,再f[j]没更新前,f[j]里储存的其实是第2行第j列的答案.f[j-1]跟朴素一样.

代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 long long n,m,n1,m1,f[22];
 7 bool a[101][101];
 8 
 9 int main() {
10     scanf("%lld%lld%lld%lld",&n,&m,&n1,&m1);
11     n++;m++;n1++;m1++;//压维后如果不加1,运算期间下标会成负数 
12     a[n1][m1] = a[n1-2][m1-1] = a[n1-1][m1-2] = a[n1-2][m1+1] = a[n1-1][m1+2] = a[n1+1][m1-2] = a[n1+2][m1-1] = a[n1+1][m1+2] = a[n1+2][m1+1] = 1;
13     f[1] = 1;
14     for(int i = 1;i <= n; i++)
15         for(int j = 1;j <= m; j++)
16             if(!a[i][j])
17                 f[j] += f[j-1];    
18             else
19                 f[j] = 0;    
20     printf("%lld",f[m]);
21     return 0;
22 }

空间优化

//好像并不优化时间