记录一个 Full of accomplishment & 纯手调了一天 的题目

P1018 乘积最大

艰辛历程

AC & 未去除调试注释 ( 不用你数，141行 )

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define ll long long 
using namespace std;
ll n,k1,a[45][45][1005],f[45][45][1005],lena[45][45],lenf[45][45],c[3005];
char s[45];
inline ll mx(ll a,ll b){return a>b?a:b;}
inline ll mx3(ll a,ll b,ll c){return (a>b)?(a>c?a:c):(b>c?b:c);}
inline void add(ll j,ll i)
{
	memset(c,0,sizeof(c));
	ll Lena=lena[j][i-1];
	for(ll k=1;k<=Lena;k++)
		c[k]=a[j][i-1][k];
//	puts("");
//	for(ll k=Lena;k>=1;k--)
//		printf("%lld",c[k]);
//	puts("");
	ll x=0;
	for(ll k=1;k<=Lena;k++)
	{
		c[k]=c[k]*10+x;
		x=c[k]/10;
		c[k]%=10;
	}
	while(x)
	{
		c[++Lena]=x%10;
		x/=10;
	}
//	for(ll k=Lena;k>=1;k--)
//		printf("%lld",c[k]);
//	puts("");
	ll Len=mx3(lena[j][i],Lena,lena[i][i]);
	for(ll k=1;k<=Len;k++)
	{
		a[j][i][k]=c[k]+a[i][i][k];
		a[j][i][k+1]+=a[j][i][k]/10;
		a[j][i][k]%=10;
	}
	if(a[j][i][Len+1])
		Len++;
	lena[j][i]=Len;
//	for(ll k=lena[j][i];k>=1;k--)
//		printf("%lld",a[j][i][k]);
//	puts("");
}
inline void mul(ll i,ll j,ll k,ll l,ll u,ll v)
{
	//-----------------------------
	memset(c,0,sizeof(c));
	ll x=0,Len=lenf[i][j]+lena[k][l];
	for(ll p=1;p<=lenf[i][j];p++)
	{
		x=0;
		for(ll t=1;t<=lena[k][l];t++)
		{
			c[p+t-1]+=f[i][j][p]*a[k][l][t]+x;
			x=c[p+t-1]/10;
			c[p+t-1]%=10;
		}
		c[p+lena[k][l]]=x;
	}
	while(c[Len]==0 && Len>1)
		Len--;
	//-----------------------------
//	for(ll k=Len;k>=1;k--)
//		printf("%lld",c[k]);
//	puts("");
	if(Len>lenf[u][v])
	{
		lenf[u][v]=Len;
		for(ll i=1;i<=lenf[u][v];i++)
			f[u][v][i]=c[i];
	}
	else if(Len==lenf[u][v])
	{
		for(ll i=Len;i>=1;i--)
		{
			if(f[u][v][i]>c[i])
				break;
			else if(f[u][v][i]<c[i])
			{
				lenf[u][v]=Len;
				for(ll j=1;j<=lenf[u][v];j++)
					f[u][v][j]=c[j];
				break;
			}
		}
	}
}
int main()
{
//	freopen("outputmy.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>k1>>(s+1);
	for(ll i=1;i<=n;i++)
	{
		a[i][i][1]=s[i]^48;
		lena[i][i]=1;
	}
	for(ll i=2;i<=n;i++)
		for(ll j=i-1;j>=1;j--)
			add(j,i);
	for(ll i=1;i<=n;i++)
	{
//		if(lena[1][i]>lenf[i][0])
		lenf[i][0]=lena[1][i];
		for(ll j=1;j<=lenf[i][0];j++)
		{
			f[i][0][j]=a[1][i][j];
//			printf("%lld",f[i][0][j]);
		}
//		for(ll j=lenf[i][0];j>=1;j--)
//			printf("%lld",f[i][0][j]);
//		puts("");
	}
	for(ll k=1;k<=k1;k++)
		for(ll i=k+1;i<=n;i++)
			for(ll j=k;j<i;j++)
			{
//				printf("k: %lld  i: %lld  j: %lld  ",k,i,j);
//				if(k==1 && i==6 && j==2)
//				{
//					for(ll x=1;x<=lenf[j][k-1];x++)
//						cout<<f[j][k-1][x];
//					cout<<endl;
//					for(ll x=1;x<=lena[j+1][i];x++)
//						cout<<a[j+1][i][x];
//					cout<<endl;
//					cout<<f[j][k-1]<<" "<<a[j+1][i]<<endl;
					mul(j,k-1,j+1,i,i,k);
//				}
			}
	for(ll i=lenf[n][k1];i>=1;i--)
		cout<<f[n][k1][i];
	cout<<endl;
	return 0;
}

AC & 去除注释 ( 不用你数，105行 )

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define ll long long 
using namespace std;
ll n,k1,a[45][45][1005],f[45][45][1005],lena[45][45],lenf[45][45],c[3005];
char s[45];
inline ll mx(ll a,ll b){return a>b?a:b;}
inline ll mx3(ll a,ll b,ll c){return (a>b)?(a>c?a:c):(b>c?b:c);}
inline void add(ll j,ll i)
{
	memset(c,0,sizeof(c));
	ll Lena=lena[j][i-1];
	for(ll k=1;k<=Lena;k++)
		c[k]=a[j][i-1][k];
	ll x=0;
	for(ll k=1;k<=Lena;k++)
	{
		c[k]=c[k]*10+x;
		x=c[k]/10;
		c[k]%=10;
	}
	while(x)
	{
		c[++Lena]=x%10;
		x/=10;
	}
	ll Len=mx3(lena[j][i],Lena,lena[i][i]);
	for(ll k=1;k<=Len;k++)
	{
		a[j][i][k]=c[k]+a[i][i][k];
		a[j][i][k+1]+=a[j][i][k]/10;
		a[j][i][k]%=10;
	}
	if(a[j][i][Len+1])
		Len++;
	lena[j][i]=Len;
}
inline void mul(ll i,ll j,ll k,ll l,ll u,ll v)
{
	memset(c,0,sizeof(c));
	ll x=0,Len=lenf[i][j]+lena[k][l];
	for(ll p=1;p<=lenf[i][j];p++)
	{
		x=0;
		for(ll t=1;t<=lena[k][l];t++)
		{
			c[p+t-1]+=f[i][j][p]*a[k][l][t]+x;
			x=c[p+t-1]/10;
			c[p+t-1]%=10;
		}
		c[p+lena[k][l]]=x;
	}
	while(c[Len]==0 && Len>1)
		Len--;
	if(Len>lenf[u][v])
	{
		lenf[u][v]=Len;
		for(ll i=1;i<=lenf[u][v];i++)
			f[u][v][i]=c[i];
	}
	else if(Len==lenf[u][v])
	{
		for(ll i=Len;i>=1;i--)
		{
			if(f[u][v][i]>c[i])
				break;
			else if(f[u][v][i]<c[i])
			{
				lenf[u][v]=Len;
				for(ll j=1;j<=lenf[u][v];j++)
					f[u][v][j]=c[j];
				break;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k1>>(s+1);
	for(ll i=1;i<=n;i++)
	{
		a[i][i][1]=s[i]^48;
		lena[i][i]=1;
	}
	for(ll i=2;i<=n;i++)
		for(ll j=i-1;j>=1;j--)
			add(j,i);
	for(ll i=1;i<=n;i++)
	{
		lenf[i][0]=lena[1][i];
		for(ll j=1;j<=lenf[i][0];j++)
			f[i][0][j]=a[1][i][j];
	}
	for(ll k=1;k<=k1;k++)
		for(ll i=k+1;i<=n;i++)
			for(ll j=k;j<i;j++)
				mul(j,k-1,j+1,i,i,k);
	for(ll i=lenf[n][k1];i>=1;i--)
		cout<<f[n][k1][i];
	cout<<endl;
	return 0;
}