#include<iostream>
using namespace std;
struct Int
{
short t;
unsigned long long u,d;
Int()
{
t=0;
u=0;
d=0;
}
Int(unsigned long long n)
{
t=0;
u=0;
d=n;
}
Int(short tt,unsigned long long uu,unsigned long long dd)
{
t=tt;
u=uu;
d=dd;
}
friend Int operator+(Int a,Int b)
{
a.t+=b.t;
if (a.u>(((unsigned long long)(1)<<63)+~((unsigned long long)(1)<<63)-b.u))
{
a.t+=1;
}
a.u+=b.u;
if (a.d>(((unsigned long long)(1)<<63)+~((unsigned long long)(1)<<63)-b.d))
{
if (a.u>(((unsigned long long)(1)<<63)+~((unsigned long long)(1)<<63)-1))
{
a.t+=1;
}
a.u+=1;
}
a.d+=b.d;
return a;
}
friend void lshift(Int&a)
{
a.t<<=1;
a.t+=(a.u&((unsigned long long)(1)<<63))>>63;
a.u<<=1;
a.u+=(a.d&((unsigned long long)(1)<<63))>>63;
a.d<<=1;
}
friend void rshift(Int&a)
{
a.d>>=1;
a.d+=(a.u&1)<<63;
a.u>>=1;
a.u+=(a.t&1)<<63;
a.t>>=1;
}
friend Int operator*(Int a,Int b)
{
Int c;
while(a.u>0||a.d>0)
{
if(a.d&1)
{
c=c+b;
}
lshift(b);
rshift(a);
}
return c;
}
friend bool operator<=(Int a,Int b)
{
if(a.t==b.t)
{
if(a.u==b.u)
{
return a.d<=b.d;
}
return a.u<b.u;
}
return a.t<b.t;
}
}dec_[42]={{0,0,1},
{0,0,10},
{0,0,100},
{0,0,1000},
{0,0,10000},
{0,0,100000},
{0,0,1000000},
{0,0,10000000},
{0,0,100000000},
{0,0,1000000000},
{0,0,10000000000},
{0,0,100000000000},
{0,0,1000000000000},
{0,0,10000000000000},
{0,0,100000000000000},
{0,0,1000000000000000},
{0,0,10000000000000000},
{0,0,100000000000000000},
{0,0,1000000000000000000},
{0,0,10000000000000000000},
{0,5,7766279631452241920},
{0,54,3875820019684212736},
{0,542,1864712049423024128},
{0,5421,200376420520689664},
{0,54210,2003764205206896640},
{0,542101,1590897978359414784},
{0,5421010,15908979783594147840},
{0,54210108,11515845246265065472},
{0,542101086,4477988020393345024},
{0,5421010862,7886392056514347008},
{0,54210108624,5076944270305263616},
{0,542101086242,13875954555633532928},
{0,5421010862427,9632337040368467968},
{0,54210108624275,4089650035136921600},
{0,542101086242752,4003012203950112768},
{0,5421010862427522,3136633892082024448},
{0,54210108624275221,12919594847110692864},
{0,542101086242752217,68739955140067328},
{0,5421010862427522170,687399551400673280},
{2,17316620476856118468,6873995514006732800},
{29,7145508105175220139,13399722918938673152},
{293,16114848830623546549,4870020673419870208}};
ostream& operator<<(ostream& out, Int a)
{
Int j=0;
bool zero_=0;
for(int i=41;i>=0;i--)
{
int t=0;
for(Int k=j;k<=a;j=k,k=k+dec_[i],t++);
t--;
if(t)
{
out<<t;
zero_=1;
}
else if(i==0||zero_)
{
out<<0;
}
}
}
Int dp[41][6];
int num[41];
int n,k;
Int getn(int l,int r)
{
Int rt=0;
for(int i=l;i<=r;i++)
{
rt=rt*10;
rt=rt+num[i];
}
return rt;
}
int main()
{
cin>>n>>k;
Int l=0;
for(int i=1;i<=n;i++)
{
char j;
cin>>j;
num[i]=j-'0';
l=l*10;
l=l+num[i];
dp[i][0]=l;
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
for(int l=1;l<j;l++)
{
dp[j][i]=dp[j][i]<=dp[l][i-1]*getn(l+1,j)?dp[l][i-1]*getn(l+1,j):dp[j][i];
}
}
}
cout<<dp[n][k]<<endl;
return 0;
}
这不是一个常规的高精。从理论上和测试样例上,它都是可行的,但是很不幸所有点都T了。
我知道正常的高精怎么写,不需要教我。我只是想知道,这种高精TLE的原因。