1922. Toothpick Arithmetic,怎么老是WA,样例和其他东西(我的自测样例)测的都对的呀,麻烦大家看一下,谢谢! (Past)

guxuan edited 1 年,8 月前

This is a past version of blog 1922. Toothpick Arithmetic,怎么老是WA,样例和其他东西(我的自测样例)测的都对的呀,麻烦大家看一下,谢谢!

include

define N 5009

using namespace std;
typedef long long ll;
ll n,f[N],g[N],chen[N];
char op[N];
void solve(ll x){
f[x]=chen[x]=x;
for(ll i=1;i<=x;++i){
ll now=chen[i]+chen[x-i]+2;
if(now<f[x]) f[x]=now,g[x]=i,op[x]=’+’;
}
for(ll i=1;i<=x;++i){
ll now=chen[i]+chen[x/i]+2;
if(x%i==0&&now<chen[x]){
chen[x]=now;
if(now<f[x])
f[x]=now,g[x]=i,op[x]=’’;
}
}
}
void output(ll x){
if(op[x]==’
’){
output(x/g[x]);
cout<<”*”;
output(g[x]);
}
else if(op[x]==’+’){
output(x-g[x]);
cout<<”+”;
for(ll i=1;i<=g[x];++i) cout<<”|”;
}
else for(ll i=1;i<=x;++i) cout<<”|”;
}
int main(){
for(ll i=1;i<=5000;++i) solve(i);
// for(ll i=1;i<=20;++i) cout<<f[i]<<” “;
// cout<<endl;
// for(ll i=1;i<=20;++i) cout<<chen[i]<<” “;
// cout<<endl;
// for(ll i=1;i<=20;++i) cout<<op[i]<<” “;
// cout<>n){
cout<<f[n]<<” toothpicks: “;
output(n);
cout<<”=”<<n<<endl;
}
return 0;
}