动态规划

很简单的动态规划，转移方程为 $f(i,j)=f(i-1,j)+f(i,j-1)$。BUT 不开 long long 见祖宗。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 25;
long long f[MAXN][MAXN];
const int d[8][2] = {-1,-2,-2,-1,-1,2,-2,1,1,-2,2,-1,1,2,2,1};

int main(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1++,y1++,x2++,y2++;
    f[1][1]=1;
    f[x2][y2]=-1;
    for(int i=0;i<8;i++)
    	if(0<x2+d[i][0]&&x2+d[i][0]<=x1&&0<y2+d[i][1]&&y2+d[i][1]<=y1)
    		f[x2+d[i][0]][y2+d[i][1]] = -1;
    for(int i=1;i<=x1;i++)
    	for(int j=1;j<=y1;j++)
    		if(i==1&&j==1) continue;
    		else if(f[i][j]==-1){
    			f[i][j]=0;continue;
			}else f[i][j]=f[i-1][j]+f[i][j-1];
	cout << f[x1][y1];
    return 0;
}