大概需要运行个一两分钟
#include<bits/stdc++.h> using namespace std; bool check(vector<int>&v,int l,int r); bool dfs(vector<int>&v,int k){ if(k==v.size()-1) return true; if(check(v,0,k)||check(v,k+1,(int)v.size()-1)) return false; return dfs(v,k+1); } bool check(vector<int>&v,int l,int r){ int cnt1 = 0,cnt2 = 0; for(int i=l;i<=r;i++) { if(v[i]==1) cnt1++; else if(v[i]==0) cnt2++; } return cnt1==cnt2; } int main(){ int n,m; cin>>n>>m; int res = 0; vector<int> v(m+n); for(int i=0;i<n;i++)v[i]=0; for(int i=n;i<m+n;i++)v[i]=1; if(dfs(v,0)) res++; while(next_permutation(v.begin(),v.end())){ if(dfs(v,0)) res++; } cout<<res; }
有了以上解析做铺垫,则解答本题只需要转换为计算(0,0)到(n,m)的所有路径条数中不经过相等点的路径条数。就是下面图中的阴影区域了(在阴影区域外则必会经过相等点)。
1ms解决…
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; //大的数字作为横轴(x轴=>列),小的数字作为纵轴(y轴=>行) // cin>>n>>m; n = 10;m = 20; int dp[n+1][m+1]; memset(dp,0,sizeof dp); //更新阴影区域的第一行。 for(int i=0;i<m-n;i++)dp[0][i] = 1; //只更新阴影区域 for(int i=1;i<=n;i++){ for(int j=i+1;j<m-n+i;j++){ dp[i][j] += dp[i-1][j]; dp[i][j] += dp[i][j-1]; } } cout<<dp[n][m-1]; }
实际上路径问题就是排列问题,很多情况下两者可以互换。
横向 4 步、纵向 3 步地移动也就是“7 步中有 4 步为横向移动”,数学上就是 C^7_4 计算可得 35 种情况。本题用的是通过反复统计从最左列和最下列到达各个交叉点的情况,得到最终解的方法。对于复杂图形而言,这是一种行之有效的方法。