10pts 求调(#2~#10WA)
查看原帖
10pts 求调(#2~#10WA)
991808
Ql001楼主2025/1/31 11:35
#include<bits/stdc++.h>
using namespace std;
signed main(){
	long long n,k,ans=1;
	char numc[45];
	long long num[45],sum[45][45];
	bool vis[45][45];
	cin>>n>>k;
	priority_queue<int,vector<int>,greater<int> >gap,q;
	memset(sum,0,sizeof(sum));
	memset(sum,0,sizeof(vis));
	//1231
	for(int i=1;i<=n;i++){
		cin>>numc[i];
		num[i]=numc[i]-'0';
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			sum[i][j]=num[i];
			for(int _j=i+1;_j<=j;_j++){
				sum[i][j]*=10;
				sum[i][j]+=num[_j];
				//cout<<i<<' '<<j<<' '<<sum[i][j]<<endl;
			}
		}
	}
	//cout<<sum[1][1]<<endl;
	//cout<<sum[1][2]<<endl;
	int l,r,mx;
	for(int i=1;i<=k;i++){
		int a,b,mid;
		if(i==1){
			l=1,r=n;
		}
		else{
			mx=-INT_MAX;
			r=0;
			while(gap.size()){
				if(mx<sum[r+1][gap.top()]){
					mx=sum[r+1][gap.top()];
					l=r+1;
					r=gap.top();
				}
				q.push(gap.top());
				gap.pop();
			}
			while(q.size()){
				gap.push(q.top());
				q.pop();
			}
		}
		mid=(l+r)/2;
		a=sum[l][mid];
		a*=sum[mid+1][r];
		b=sum[l][mid+1];
		b*=sum[mid+2][r];
		if(a>b)gap.push(mid);
		else gap.push(mid+1);
	} 
	l=1;
	while(gap.size()){
		//cout<<l<<' '<<gap.top()<<' '<<sum[l][gap.top()]<<endl;
		ans*=sum[l][gap.top()];
		l=gap.top()+1;
		gap.pop();
	}
	ans*=sum[l][n];
	cout<<ans;
	return 0;
}
2025/1/31 11:35
加载中...