分治法4思维导图

这题许多方法都可以做，这里讲dp的（其实 思路都没区别，就是代码实现的区别）。定义 一个f数组，f[i][j]表示传j次到第i个人手上有 几种方案。每个人拿到剑都是从左右两边拿到 的，所以得出动态转移方程式f[i][j]=f[i-1][j-1 ]+f[i+1][j-1]（注意f[1][j]和f[n][j]要特殊处理。边界就是f[1][0]=1

a[1][0]=1; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(j==1) a[j][i]=a[n][i-1]+a[2][i-1]; else if(j==n) a[j][i]=a[1][i-1]+a[n-1][i-1]; else a[j][i]=a[j-1][i-1]+a[j+1][i-1]; } }

这就是宇宙的尺度1的一个翻版，只不过是模板变了一下，我们只需要改一下模板存储，按照他存储的来赋值就行了，中间有许多细节点，见注释

#include<bits/stdc++.h> using namespace std; char a[730][730]; string mu[10]; int n; void dfs(int n,int x,int y){ if(n==1){//赋值方式改了一下，由原来的赋值单个字符到现在赋值一组 for(int i=0;i<n;i++) for(int j=0;j<n;j++) a[i+x][j+y]=mu[i][j]; return; return ; } int l=pow(3,n-2); dfs(n-1,x,y); dfs(n-1,x+2*l,y); dfs(n-1,x+2*l,y+2*l); dfs(n-1,x+l,y+l); dfs(n-1,x,y+2*l); } int main(){ while(1){ int s; cin>>s; if(s==-1) break; getchar(); //吃换行 for(int i=0;i<s;i++){//从0开始是为了后面循环的统一，因为字符串都是从0开始的 getline(cin,mu[i]); } int t; cin>>t; dfs(s,0,0);//注意是0,0不是1,1 for(int i=0;i<pow(s,t);i++){ for(int j=0;j<pow(s,t);j++){ if(a[i][j]==0) cout<<' '; else cout<<a[i][j]; } cout<<endl; } } return 0; }