POJ 1923 Fourier‘s Lines G++dfs记忆搜索 背

xiaoxiao2021-02-28  113

#include <iostream> #include <cstdio> #include <cstring> using namespace std; //英语 看博友好分析 抄博友程序 dfs记忆搜索 背 int dp[104][10010]; int dfs(int n,int m) { if(m>(n*(n-1))/2 || m<0) { return 0; } if(m==0|| m==(n*(n-1))/2) { return 1; } if(dp[n][m]!=-1) { return dp[n][m]; } for(int i=1;i<n;i++)//抄博友程序 枚举平行的边数i { if(dfs(n-i,m-(n-i)*i)) { return dp[n][m]=1; } } return dp[n][m]=0;; } int main() { int tag=0; while(1) { tag++; memset(dp,-1,sizeof(dp)); int n,m; cin>>n>>m; if(n==0 &&m==0) { break; } if(dfs(n,m)) { cout<<"Case "<<tag<<": "<<n<<" lines with exactly "<<m<<" crossings can cut the plane into "<<n+m+1<<" pieces at most."<<endl; }else { cout<<"Case "<<tag<<": "<<n<<" lines cannot make exactly "<<m<<" crossings."<<endl; } } return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-53444.html

最新回复(0)