过了后面三个测试点0pts,用的dfs(其他全都是WA)
查看原帖
过了后面三个测试点0pts,用的dfs(其他全都是WA)
1075989
BlauAnthony楼主2025/1/1 18:43
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,k;string s,maxs;
string nows;
void alltimes(int now,vector<int> &sk,int w){
	if(now==k+1){
		if(nows.size()>maxs.size()){
			maxs=nows;
		}else if(nows.size()<maxs.size()){
		}else{
			for(int i=maxs.size()-1;i>=0;i--){
				if(maxs[i]>nows[i]){
					break;
				}else if(maxs[i]<nows[i]){
					maxs=nows;
					break;
				}
			} 
		}
	}else{
		string addstr;
		int tmp,jw;
		for(int i=w;i<n;i++){
			if(i==0||sk[i-1]==1){
				alltimes(now+1,sk,i);
				break;
			}else{
				addstr="";jw=0;
				for(int j=0;j<nows.size();j++){
					tmp=(nows[j]-'0')*(s[i]-'0')+jw;
					jw=tmp/10;
					tmp%=10;
					addstr+=tmp;
				}
				jw=0;
				for(int j=w;j<addstr.size()+w;j++){
					if(j>=nows.size())nows+='0';
					tmp=(addstr[j-w]-'0')+(nows[j]-'0')+jw;
					jw=tmp/10;
					tmp%=10;
					nows[j]=tmp;
				}
			}
		}
	}
}
void dfs(int now,vector<int> &sk,int w){
	for(int i=w;i<n-1;i++){
		sk[i]=1;
		nows="0";
		if(now==k-1)alltimes(0,sk,0);
		else dfs(now+1,sk,i+1);
		sk[i]=0;
	}
}
int main(){
	cin>>n>>k>>s;maxs='0';nows='0';
	vector<int> sk(n-1);
	for(int i=0;i<s.size()/2;i++)swap(s[i],s[s.size()-i-1]);
	dfs(0,sk,0);
	for(int i=maxs.size()-1;i>=0;i--)cout<<maxs[i];
	return 0;
} 
2025/1/1 18:43
加载中...