P1018最大乘积(咋报错了啊┭┮﹏┭┮)
  • 板块学术版
  • 楼主nzynzy
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/8/27 14:37
  • 上次更新2023/11/4 08:49:31
查看原帖
P1018最大乘积(咋报错了啊┭┮﹏┭┮)
211960
nzynzy楼主2021/8/27 14:37
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=2005;
vector<int> f[N][N];
string s;
int n,k;
vector<int> cs(int l,int r){
	vector<int>c;
	for(int i=r;i>=l;i--){
		c.push_back(s[i]-'0');
	}
	return c;
}
vector<int> mul(vector<int> &a,vector<int> &b){
	int t=0;
	vector<int>c;
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b.size();j++){
			c[i+j]+=a[i]*b[j];
		}
	}
	for(int i=0;i<c.size();i++){
		t+=c[i];
		c[i]=t%10;
		t/=10;
	}
	while(c.size()>1&&c.back()==0)c.pop_back();
	return c;
}
vector<int> cmp(vector<int> &a,vector<int> &b){
	if(a.size()>b.size())return a;
	if(a.size()<b.size())return b;
	for(int i=a.size()-1;i>=0;i--){
		if(a[i]>b[i])return a;
		if(a[i]<b[i])return b;
	}
	return a;
}
int main(){
	cin>>n>>k;
	cin>>s;
	s=' '+s;
	for(int i=1;i<=n;i++)f[i][0]=cs(1,i);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=min(k,i-1);j++){
			for(int h=j+1;h<=i;h++){
				f[i][j]=cmp(f[i][j],mul(f[h-1][j-1],cs(h,i)));
			}
		}
	}
for(int i=f[n][k].size()-1;i>=0;i--)cout<<f[n][k][i];
	return 0;
}
2021/8/27 14:37
加载中...