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

guxuan edited 1 年,6 月前

include

define N 5009

define INF 1e15

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]=’+’;
// }
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;
}
}
void output(ll x){
if(chen[x]==x){for(ll i=1;i<=x;++i) cout<<”|”;}
else{output(x/g[x]);cout<<”
“;output(g[x]);}
}
void oup(ll x){
ll s=0,num=chen[x];
for(ll i=1;i<=x;++i)
if(i+chen[x-i]+2<num) num=i+chen[x-i]+2,s=i;
if(num==1) cout<<”1 toothpick: “;
else cout<<num<<” toothpicks: “;
output(x-s);
if(s!=0) cout<<”+”;
for(ll i=1;i<=s;++i) cout<<”|”;
}
int main(){
for(ll i=1;i<=5000;++i) solve(i);
while(cin>>n){
oup(n);
cout<<”=”<<n<<endl;
}
return 0;
}

Past Versions

Comments