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

guxuan edited 3 年,11 月前

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

include

define N 5009

define INF 1e15

using namespace std;
typedef long long ll;
ll n,f[N],g[N],chen[N],yilai[N];
char op[N];
void solve(){
for(ll x=1;x<=5000;++x){
chen[x]=x;
for(ll i=2;ii<=x;++i){
ll now=chen[i]+chen[x/i]+2;
if(x%i==0&&now<chen[x]) chen[x]=now,g[x]=i;
}
}
for(ll i=1;i<=5000;++i){
if(chen[i]=1;–j){
ll now=f[j]+chen[i-j]+2;
if(now<f[i]) f[i]=now,yilai[i]=j,op[i]=’+’;
}
for(ll j=2;j
j<=i;++j){
ll now=chen[j]+chen[i/j]+2;
if(i%j==0&&now<f[i]) f[i]=now,yilai[i]=j,op[i]=’’;
}
}
}
void output(ll x){
if(op[x]==’
’){
output(yilai[x]);
cout<<”x”;
output(x/yilai[x]);
}else if(op[x]==’+’){
output(yilai[x]);
cout<<”+”;
output(x-yilai[x]);
}else for(ll i=1;i<=x;++i) cout<<”|”;
}
int main(){
solve();
while(cin>>n){
if(f[n]>1) cout<<f[n]<<” toothpicks: “;
else cout<<”1 toothpick : “;
output(n);
cout<<”=”<<n<<endl;
}
return 0;
}
//Case 6004: wrong output line
//WRONG OUTPUT