| 记录编号 |
280993 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
乘法问题 |
最终得分 |
100 |
| 用户昵称 |
 YGOI_真神名曰驴蛋蛋 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.842 s |
| 提交时间 |
2016-07-10 21:27:28 |
内存使用 |
100.91 MiB |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <cassert>
#include <string>
#include <cstdlib>
using namespace std;
typedef long long ll;
const ll sll=sizeof(ll);
const ll MAXLENGTH=200;
inline ll max(const ll&a,const ll&b){return a<b?b:a;}
inline void Swap(long long &a,long long &b){a=a^b;b=a^b;a=a^b;}
struct Longer{
#define LOWBIT 1000000000
int size,down;
ll num[MAXLENGTH];
Longer(const ll&a=0){size=0;ll p=a;memset(num,0,sizeof(num));while(p){num[++size]=p%LOWBIT;p/=LOWBIT;}}
void set(){down=-1;}
};
Longer operator +(const Longer&,const Longer&);
Longer operator -(const Longer&,const Longer&);
Longer operator *(const Longer&,const Longer&);
Longer operator /(const Longer&,const Longer&);
Longer operator /(const Longer&,const ll&);
Longer operator <<(const Longer&,const ll&);
Longer operator >>(const Longer&,const ll&);
bool operator <(const Longer&,const Longer&);
bool operator >(const Longer&,const Longer&);
bool operator >=(const Longer&,const Longer&);
bool operator <=(const Longer&,const Longer&);
bool operator !=(const Longer&,const Longer&);
bool operator ==(const Longer&,const Longer&);
void read(Longer &);
void put(const Longer&);
Longer exchange(const Longer&);
Longer exchange(const Longer&a){
Longer c;
c.size=a.size;
for(int i=1;i<=a.size;++i)
c.num[i]=a.num[a.size-i+1];
return c;
}
Longer operator <<(const Longer&a,const ll&b){
Longer c;
c.size=a.size+b;
for(int i=1;i<=a.size;++i)
if( i+b <MAXLENGTH )c.num[i+b]=a.num[i];
return c;
}
Longer operator >>(const Longer&a,const ll&b){
Longer c;
c.size=max(1,a.size-b);
for(int i=b+1;i<=a.size;++i)
c.num[i-b]=a.num[i];
return c;
}
Longer operator +(const Longer &a,const Longer &b){
Longer c;
c.size=max(a.size,b.size);
for(int i=1;i<=c.size;++i)
c.num[i]=a.num[i]+b.num[i];
for(int i=1;i<=c.size;++i){
c.num[i+1]+=c.num[i]/LOWBIT;
c.num[i]%=LOWBIT;
}
while(c.num[c.size+1]!=0)c.size++;
return c;
}
Longer operator -(const Longer &a,const Longer &b){
if(a<b)return 0;
Longer c;
c.size=max(a.size,b.size);
for(int i=1;i<=c.size;++i)
c.num[i]=a.num[i]-b.num[i];
for(int i=1;i<=c.size;++i)
if(c.num[i]<0){
c.num[i]+=LOWBIT;
--c.num[i+1];
}
while(c.num[c.size]==0&&c.size>0)--c.size;
return c;
}
Longer operator *(const Longer &a,const Longer &b){
Longer c;
c.size=a.size+b.size-1;
for(int i=1;i<=a.size;++i)
for(int j=1;j<=b.size;++j)
c.num[i+j-1]+=a.num[i]*b.num[j];
for(int i=1;i<=c.size;++i){
c.num[i+1]+=c.num[i]/LOWBIT;
c.num[i]%=LOWBIT;
}
if(c.num[c.size+1]!=0)c.size++;
return c;
}
Longer operator / (const Longer&a,const ll&b){
if(b==1)return a;
ll d=0;
Longer c;
c.size=a.size;
for(int i=c.size;i>=1;--i){
c.num[i]=(d*LOWBIT+a.num[i])/b;
d=(d*LOWBIT+a.num[i])%b;
}
while(c.num[c.size]==0&&c.size>0)--c.size;
return c;
}
Longer operator / (const Longer &_a,const Longer &_b){
if(_b==1)return _a;
Longer l=1,r=1,mid,p,a=_a,b=_b;
if(b==0){printf("Runtime Error in Big Integer :: the devided number cannot be zero.\n");abort();}
if(a==0||a<b)return 0;
ll k=max(a.size-b.size,0);
l=l<<(k-1);
r=r<<(k+1);
//put(l);put(r);
while(l<r){
mid=((l+r)/2);
p=mid*b;
if(p==a)return mid;
else if(p>a)r=mid+(-1);
else l=mid+1;
}
if(l*b>a)return l-1;
return l;
}
bool operator <(const Longer&a,const Longer&b){
if(a.size!=b.size)return a.size<b.size;
for(int i=a.size;i>=1;--i)
if(a.num[i]!=b.num[i])
return a.num[i]<b.num[i];
return 0;
}
bool operator >(const Longer&a,const Longer&b){return b<a;}
bool operator >=(const Longer&a,const Longer&b){return a>b||a==b;}
bool operator <=(const Longer&a,const Longer&b){return a<b||a==b;}
bool operator !=(const Longer&a,const Longer&b){return !(a==b);}
bool operator ==(const Longer &a,const Longer&b){return !(a<b)&&!(b<a);}
void read(Longer &t){t=0;
std::string s;
std::cin>>s;
int sizen=s.length();
// printf("\n\nsizen->%d\n\n",sizen);
int p=sizen%9,i=0;ll k=0;
t.size=sizen/9+(sizen%9!=0);
if(p!=0){for(i=0;i<p;++i)k=k*10+s[i]-'0'; t.num[t.size--]=k; k=0;}
while(t.size){
p=i+9;
for(i;i<p;++i)k=k*10+s[i]-'0';
t.num[t.size--]=k;k=0;
}t.size=sizen/9+(sizen%9!=0);
t=t+0;
}
void put(const Longer &k){
printf("%lld",k.num[k.size]);
for(int i=k.size-1;i>=1;--i)
printf("%09lld",k.num[i]);
}
Longer ans[40][40][40];
Longer w[40][40];
char s[40];
Longer slove(int i,int j,int k){
//printf("%d %d %d\n",i,j,k);
if(k==0){return ans[i][j][k]=w[i][j];}
if(ans[i][j][k].down!=-1)return ans[i][j][k];
for(int ii=i;ii<=j;++ii)
for(int kk=0;kk<k;++kk)
ans[i][j][k]=std::max(ans[i][j][k],slove(i,ii,kk)*slove(ii+1,j,k-kk-1));
ans[i][j][k].down=0;
return ans[i][j][k];
}
int doing(){
freopen("chf.in","r",stdin);freopen("chf.out","w",stdout);
int n,k;
scanf("%d %d %s",&n,&k,s+1);
for(int i=0;i<40;++i)
for(int j=0;j<40;++j)
for(int k=0;k<40;++k)
ans[i][j][k].set();
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
w[i][j]=w[i][j-1]*10+(s[j]-'0');
put(slove(1,n,k));
return 0;
}
int ppt=doing();
int main(){;}