60WA求助P1002过河卒
查看原帖
60WA求助P1002过河卒
981551
DGFLSzfd楼主2024/7/17 21:38
#include<bits/stdc++.h>
using namespace std;
int bx,by,cx,cy;
map<int,map<int,long long> >dp;
int main()
{
	cin>>bx>>by>>cx>>cy;
	dp[0][0]=1;
	
	dp[cx][cy]=-1e3; 
	dp[cx+2][cy+1]=-1e3; dp[cx+1][cy+2]=-1e3; dp[cx-1][cy+2]=-1e3; dp[cx-2][cy+1]=-1e3; 
	dp[cx-2][cy-1]=-1e3; dp[cx-1][cy-2]=-1e3; dp[cx+1][cy-2]=-1e3; dp[cx+2][cy-1]=-1e3; 
	for(int i=1;i<24;i++) 
	{
		dp[0][i]=dp[0][i-1];
		dp[i][0]=dp[i-1][0];
	}
	
	for(int i=1;i<=bx;i++)
	{
		for(int j=1;j<=by;j++)
		{
			if(dp[i][j]<0) continue;
			dp[i][j]=max(dp[i][j],max(dp[i-1][j],max(dp[i][j-1],dp[i-1][j]+dp[i][j-1]) ) ) ;
			//cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;  system("pause");
		} 
	} 
//	for(int i=0;i<=bx;i++)
//	{
//		for(int j=0;j<=by;j++)
//		{
//			cout<<dp[i][j]<<' ';
//		}cout<<endl;
//	}
	cout<<max(0ll,dp[bx][by]);
} 

感觉map有点取巧,但又看不出有何不妥

2024/7/17 21:38
加载中...