哪些购物网站有做拼团活动,专门制作网页的工具,网站建设培训公司排名,博物馆网站制作题目#xff1a;UVA-10253 题目翻译#xff08;来自蓝书#xff09;#xff1a; 串并联网络有两个端点#xff0c;一个叫源#xff0c;一个叫汇#xff0c;递归定义如下#xff1a;
#xff08;1#xff09; 一条单独的边是串并联网络。
#xff08;2#xff09;…题目UVA-10253 题目翻译来自蓝书 串并联网络有两个端点一个叫源一个叫汇递归定义如下
1 一条单独的边是串并联网络。
2 若G1和G2是串并联网络把它们的源和源接在一起、汇接在一起也能得到串并联网络。
3 若G1和G2是串并联网络把G1的汇和G2的源接在一起也能得到串并联网络。
其中规则2指的是并联、规则3指的是串联。串并联网络中两点之间可以有多条边串联或者并联在一起的各个部分可以任意调换顺序。
输入正整数n(1n30)统计有多少个n条边的串并联网络。
思路基本和蓝书的思路一致不过我用的是记忆化搜索的写法不想抄代码想用自己的代码风格去写
d[i][j]sum{C(f(i)p-1,p)dp[i-1][j-pi] | p*ij} 主要递推式。 其中fidp[i-1][i],如果i1的话 f1 1 细节可看代码。
#includebits/stdc.h
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod1000000000;
const ll N 1e510;
const double eps 1e-4;
const double piacos(-1);
ll gcd(int a,int b){return !b?a:gcd(b,a%b);}
ll dp[50][50];
ll c(ll n,ll m)//组合数
{ll ans1;for(ll i1;im;i){ans*(n-i1);ans/i;}return ans;
}
ll dfs(ll i,ll j)
{if(j0) return 1;//边界条件一定要思考好if(ij1) return 1;if(i0) return 0;if(dp[i][j]-1){return dp[i][j];}ll ansdp[i][j];ans0;for(ll k0;k*ij;k){if(i1) ans(dfs(i-1,j-(k*i)));//i1 的情况f(1)1;else ans(dfs(i-1,j-(k*i))*c(dfs(i-1,i)k-1,k));}return ans;
}
void slove()
{ll n;FILL(dp,-1);while(cinnn){if(n1) cout1endl;else cout2*dfs(n-1,n)endl;}
}
int main()
{iosint t1;//cint;while(t--){slove();}return 0;
}
