subtask
luogu
4 2
1231
62
Nail
5 4
23243
144
5 3
23243
768
5 2
23243
2784
CCF
6 1
101010
10100
9 4
321044105
5166000
8 3
22222222
234256
10 5
7777777777
1722499009
code
my code
ver1: 0 Unaccepted
link: record 150148499
ver2: 100 Unaccepted
add: getchar();getchar();
link: record 150167935
rule: luogu1; luogu2
ver3: 100 Accepted
add: if(ntable[compmax][nmultiple+1][0]==0) printf("0");
link: record 150289485
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define ulli unsigned long long int
short ntable[40+10][6+10][100005];
short datum[40+10];
short tempcompare[40+10][100005];
int nlength,nmultiple;
void fmul(int jD,int kD,int fromxT,int fromyT,int toC){
//datum[jD~kD] * ntable[fromxT][fromyT][...] -> tempcompare[toC][...]
vector<short> res(ntable[fromxT][fromyT][0]+kD-jD+40+6+10,0);
int eachmul;
for(int i=kD;i>=jD;i--)
for(lli j=ntable[fromxT][fromyT][0];j>=1;j--){
eachmul=ntable[fromxT][fromyT][j]*datum[i];
res[i+j]+=eachmul;
res[i+j-1]+=res[i+j]/10;
res[i+j]%=10;
}
ulli lastNotZero;
if(res[0]==0)
for(lastNotZero=0;lastNotZero<res.size();lastNotZero++)
if(res[lastNotZero]!=0)
break;
for(ulli i=lastNotZero,ii=1;i<res.size();i++,ii++)
tempcompare[toC][ii]=res[i];
tempcompare[toC][0]=kD+ntable[fromxT][fromyT][0]-lastNotZero+1;
return;
}
bool fcompare(int suppmax,int n){
//tempcompare[suppmax][...] < tempcompare[n][...] -> true
if(tempcompare[suppmax][0]<tempcompare[n][0]) return true;
if(tempcompare[suppmax][0]>tempcompare[n][0]) return false;
for(int i=1;i<=tempcompare[suppmax][0];i++){
if(tempcompare[suppmax][i]==tempcompare[n][i])
continue;
else if(tempcompare[suppmax][i]<tempcompare[n][i])
return true;
else
return false;
}
return false;
}
bool fcompare2(int suppmax,int n){
//ntable[suppmax][nmultiple+1][...] < ntable[n][nmultiple+1][...] -> true
if(ntable[suppmax][nmultiple+1][0]<ntable[n][nmultiple+1][0]) return true;
if(ntable[suppmax][nmultiple+1][0]>ntable[n][nmultiple+1][0]) return false;
for(int i=1;i<=ntable[suppmax][nmultiple+1][0];i++){
if(ntable[suppmax][nmultiple+1][i]==ntable[n][nmultiple+1][i])
continue;
else if(ntable[suppmax][nmultiple+1][i]<ntable[n][nmultiple+1][i])
return true;
else
return false;
}
return false;
}
int main(){
scanf("%d %d",&nlength,&nmultiple);
getchar();getchar();
for(int i=1;i<=nlength;i++){
datum[i]=getchar()-'0';
}
for(int i=1;i<=nlength;i++){
int j;
for(j=1;j<=i;j++){
ntable[i][1][j]=datum[j];
}
ntable[i][1][0]=j-1;
}
for(int j=2;j<=nmultiple+1;j++){
for(int i=j;i<=nlength;i++){
int icompstart=j-1; //ntable[j-1][j-1]~ntable[i-1][j-1]
int icomp;
for(icomp=icompstart;icomp<i;icomp++){
fmul(icomp+1,i,icomp,j-1,icomp);
/*
for(int k=0;k<=6;k++){
cout << tempcompare[icomp][k];
}
cout << "\n";
*/
}
int compmax=icompstart;
for(int iicomp=icompstart+1;iicomp<icomp;iicomp++){
if(fcompare(compmax,iicomp))
compmax=iicomp;
}
//tempcompare[compmax][...] -> ntable[i][j][...]
for(int k=0;k<=tempcompare[compmax][0];k++)
ntable[i][j][k]=tempcompare[compmax][k];
}
}
int compmax=nmultiple+1;
for(int i=nmultiple+2;i<=nlength;i++){
if(fcompare2(compmax,i))
compmax=i;
}
for(int k=1;k<=ntable[compmax][nmultiple+1][0];k++)
cout << ntable[compmax][nmultiple+1][k];
if(ntable[compmax][nmultiple+1][0]==0)
printf("0");
/*
for(int j=0;j<=6;j++){
for(int i=0;i<=8;i++){
//cout << ntable[i][j] << " ";
for(int k=0;k<=6;k++){
cout << ntable[i][j][k];
}
cout << ", ";
}
cout << endl;
}
//*/
return 0;
}
AC code
from https://www.luogu.com.cn/discuss/646733
#include<bits/stdc++.h>
using namespace std;
string s1;
int m[1001],n[1001],N[200],s[80],K;
struct data {
int num[100];
} f[60][60],ans,a[50][50];
bool cmp(int x[],int y[]) {
if(x[0]!=y[0])
return x[0]>y[0];
for(int p=x[0]; p>=1; p--) {
if(x[p]>y[p]) {
return 1;
}
if(x[p]<y[p]) {
return 0;
}
}
return 0;
}
void mul(int n[],int m[]) {
int j1,j2;
memset(s,0,sizeof(s));
s[0]=n[0]+m[0];
for(j1=1; j1<=n[0]; j1++) {
for(j2=1; j2<=m[0]; j2++) {
s[j1+j2-1]+=n[j1]*m[j2];
s[j1+j2]+=s[j1+j2-1]/10;
s[j1+j2-1]%=10;
}
}
while(!s[s[0]])
{
s[0]--;
}
}
void record(int p1,int p2)
{
int i,j=0;
a[p1][p2].num[0]=p2-p1+1;
for(i=p1;i<=p2;i++)
{
a[p1][p2].num[++j]=N[i];
}
}
int main() {
cin>>N[0]>>K;
int i,j,k;
cin>>s1;
for(i=N[0],j=0;i>=1;i--,j++)
{
N[i]=int(s1[j]-'0');
}
for(i=1;i<=N[0];i++)
{
for(j=i;j<=N[0];j++)
{
record(i,j);
}
}
for(i=1;i<=N[0];i++)
{
memcpy(f[i][0].num,a[1][i].num,sizeof(a[1][i].num));
}
for(k=1;k<=K;k++)
{
for(i=k+1;i<=N[0];i++)
{
for(j=k;j<i;j++)
{
memset(s,0,sizeof(s));
mul(f[j][k-1].num,a[j+1][i].num);
bool flag=cmp(s,f[i][k].num);
if(flag)
memcpy(f[i][k].num,s,sizeof(s));
}
}
}
for(i=f[N[0]][K].num[0];i>=1;i--)
{
cout<<f[N[0]][K].num[i];
}
if(f[N[0]][K].num[0]<1)cout<<0;//新加上这一句
return 0;
}
same question
from https://www.luogu.com.cn/discuss/764326
#include<bits/stdc++.h>
using namespace std;
struct Int{
int len;
short num[500];
int operator[](int a){
return num[a];
}void operator=(int a){
this->len=0;
memset(this->num,0,sizeof(this->num));
while(a){
this->num[++this->len]=a%10;
a/=10;
}
}
};
Int operator+(Int a,Int b){
int m=0;
if(a.len<b.len)swap(a,b);
for(int i=1;i<=a.len;i++){
a.num[i]+=b[i]+m;
m=a[i]/10;a.num[i]%=10;
}if(m>0)a.num[++a.len]=m;
return a;
}Int operator*(Int a,Int b){
Int c;c.len=0;int m=0;
memset(c.num,0,sizeof(c.num));
for(int i=1;i<=a.len;i++){
for(int j=1;j<=b.len;j++){
c.num[i+j-1]+=a[i]*b[j];
if(c[i+j-1])c.len=max(c.len,i+j-1);
}
}for(int i=1;i<=c.len;i++){
c.num[i]+=m;m=c[i]/10;c.num[i]%=10;
}while(m){
c.num[++c.len]=m;
m=c[c.len]/10;
c.num[c.len]%=10;
}return c;
}Int operator+(Int a,int b){
Int c;c=b;
return a+c;
}Int operator*(Int a,int b){
Int c;c=b;
return a*c;
}bool operator<(Int a,Int b){
if(a.len!=b.len)return a.len<b.len;
for(int i=a.len;i>0;i--){
if(a[i]!=b[i])return a[i]<b[i];
}return false;
}bool operator==(Int a,Int b){
if(a.len!=b.len)return false;
for(int i=1;i<=a.len;i++){
if(a[i]!=b[i])return false;
}return true;
}bool operator>(Int a,Int b){
if(a<b)return false;
else if(a==b)return false;
else return true;
}bool operator<=(Int a,Int b){
return !(a>b);
}bool operator>=(Int a,Int b){
return !(a<b);
}istream &operator>>(istream &in,Int &a){
char l[500];cin>>l;a.len=strlen(l);
memset(a.num,0,sizeof(a.num));
int al=a.len,ll=0;
while(al>0&&ll<a.len){
a.num[al]=l[ll]-'0';
al--;ll++;
}return in;
}ostream &operator<<(ostream &out,Int a){
for(int i=a.len;i>0;i--){
cout<<a[i];
}return out;
}Int max(Int a,Int b){
return a>b?a:b;
}Int min(Int a,Int b){
return a<b?a:b;
}
Int dp[50][10],m[50][50];int a[50],n,k;
int main(){
cin>>n>>k;getchar();
for(int i=1;i<=n;i++){
a[i]=getchar()-'0';
dp[i][1]=dp[i-1][1]*10+a[i];
}for(int i=1;i<=n;i++){
m[i][i]=a[i];
for(int j=i+1;j<=n;j++){
m[i][j]=m[i][j-1]*10+a[j];
}
}for(int i=1;i<=n;i++){
for(int j=2;j<=k+1;j++){
if(i<j)break;
for(int l=1;l<i;l++){
if(l<j-1)continue;
dp[i][j]=max(dp[i][j],dp[l][j-1]*m[l+1][i]);
}
}
}cout<<dp[n][k+1];
if(dp[n][k+1].len==0)cout<<0;
return 0;
}
LJZ's code
#include<bits/stdc++.h>
#define N 50
#define K 10
#define L 506
using namespace std;
struct num{
int v[L];
int len;
num(){
len=0;
memset(v,0,sizeof(v));
}
};
int a[N];
num G[N][N];
num dp[N][K];
num g(int x,int y){
num cnt;
for(int i=y;i>=x;i--){
cnt.len++;
cnt.v[cnt.len-1]=a[i];
}
return cnt;
}
num maxn(num x,num y){
if(x.len>y.len) return x;
if(x.len<y.len) return y;
for(int i=x.len-1;i>=0;i++){
if(x.v[i]>y.v[i]) return x;
if(x.v[i]<y.v[i]) return y;
}
return x;
}
num mult(num x,num y){
num z;
memset(z.v,0,sizeof(z.v));
z.len=x.len+y.len;
for(int i=0;i<x.len;i++)
for(int j=0;j<y.len;j++)
z.v[i+j]+=x.v[i]*y.v[j];
for(int i=0;i<z.len;i++)
if(z.v[i]>9){
z.v[i+1]+=(z.v[i]/10);
z.v[i]%=10;
}
while(z.v[z.len-1]==0 && z.len!=1) z.len--;
return z;
}
int main(){
memset(a,0,sizeof(a));
int n,k;
num tmp;
string c;
scanf("%d%d",&n,&k);
cin>>c;
for(int i=0;i<c.length();i++)
a[i+1]=c[i]-'0';
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
G[i][j]=g(i,j);
for(int i=1;i<=n;i++) dp[i][0]=G[1][i];
for(int j=1;j<=k;j++)
for(int i=j+1;i<=n-k+j;i++)
for(int l=i-1;l>=j;l--)
dp[i][j]=maxn(mult(dp[l][j-1],G[l+1][i]),dp[i][j]);
for(int i=dp[n][k].len-1;i>=0;i--)
printf("%d",dp[n][k].v[i]);
return 0;
}