#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=6100; string ans=""; int dp[N]; int dv[N]; string f(int x,string s){ if (x==0) return ""; if (x==1) return s; if (dv[x]==0){ string cur=""; for (int i=0;i<x;i++) cur+=s; return cur; } if (dv[x]>0){ return f(dv[x],s)+f(x-dv[x],s); } int d=-dv[x]; string cur=""; cur+=char(d+'0'); cur+="["; cur+=f(x/d,s); cur+="]"; return cur; } string to_str(int x){ if (x==0) return "0"; string s=""; while (x){ s+=char(x%10+'0'); x/=10; } reverse(s.begin(),s.end()); return s; } int cnt=0; void rec(int n){ if (n==1){ ans+="BDF"; return; } if (n==2){ ans+="BBDFDBDFF"; return; } ans+="BB"; rec(n-2); ans+=f(n-2,"DB"); ans+="DD"; ans+=f(n-1,"FBFD"); ans+="F"; // ans+=f(n,"F"); } //int dp[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; dp[0]=0; dp[1]=4; for (int i=2;i<=n;i++){ dp[i]=i*4; dv[i]=0; for (int j=1;j<i;j++) { if (dp[i-j]+dp[j]<dp[i]){ dp[i]=dp[i-j]+dp[j]; dv[i]=j; } } for (int j=1;j<=9;j++){ if (i%j==0){ if (dp[i/j]+3<dp[i]){ dp[i]=dp[i/j]+3; dv[i]=-j; } dp[i]=min(dp[i],dp[i/j]+3); } } } // cout<<dp[n]<<endl; rec(n); // ans=f(80,"BDDF"); cout<<ans<<endl; // cout<<ans.size()<<endl; return 0; } //9[9[BD]]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=6100; string ans=""; int dp[N]; int dv[N]; string f(int x,string s){ if (x==0) return ""; if (x==1) return s; if (dv[x]==0){ string cur=""; for (int i=0;i<x;i++) cur+=s; return cur; } if (dv[x]>0){ return f(dv[x],s)+f(x-dv[x],s); } int d=-dv[x]; string cur=""; cur+=char(d+'0'); cur+="["; cur+=f(x/d,s); cur+="]"; return cur; } string to_str(int x){ if (x==0) return "0"; string s=""; while (x){ s+=char(x%10+'0'); x/=10; } reverse(s.begin(),s.end()); return s; } int cnt=0; void rec(int n){ if (n==1){ ans+="BDF"; return; } if (n==2){ ans+="BBDFDBDFF"; return; } ans+="BB"; rec(n-2); ans+=f(n-2,"DB"); ans+="DD"; ans+=f(n-1,"FBFD"); ans+="F"; // ans+=f(n,"F"); } //int dp[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; dp[0]=0; dp[1]=4; for (int i=2;i<=n;i++){ dp[i]=i*4; dv[i]=0; for (int j=1;j<i;j++) { if (dp[i-j]+dp[j]<dp[i]){ dp[i]=dp[i-j]+dp[j]; dv[i]=j; } } for (int j=1;j<=9;j++){ if (i%j==0){ if (dp[i/j]+3<dp[i]){ dp[i]=dp[i/j]+3; dv[i]=-j; } dp[i]=min(dp[i],dp[i/j]+3); } } } // cout<<dp[n]<<endl; rec(n); // ans=f(80,"BDDF"); cout<<ans<<endl; // cout<<ans.size()<<endl; return 0; } //9[9[BD]] |