菜鸡的题解014——乘积最大

菜鸡的我动态规划写了好长时间还是参考了大佬的代码，呜呜呜

这题我觉得更适合用DFS写，思路会比较清晰。

下面给出我的两种代码

动态规划：

动态规划我太不熟练了。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
int n,k;char a[50];ll maxn;
ll b[45][10];
ll sum(int x,int y){
	int d=0;
	for(int i=x;i<=y;i++)d=d*10+a[i]-'0';
	return d;
}
int main(){
    cin>>n>>k;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    a[1]=c;
    for(int i=2;i<=n;i++)a[i]=getchar();
    for(int i=1;i<=n;i++){
    	b[i][0]=sum(1,i);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k&&i-1>=j;j++){
			for(int k=1;k<i;k++){
				if(b[k][j-1]*sum(k+1,i)>b[i][j])b[i][j]=b[k][j-1]*sum(k+1,i);
			}
			//cout<<b[i][j]<<" ";
		}
		//cout<<endl;
	}
	cout<<b[n][k];
}

DFS：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
int n,k;char a[50];ll maxn;
void dfs(int x,int y,ll s){
	//cout<<x<<" "<<y<<" "<<s<<endl;
	if(y==k){
		int sum=0;
		for(int i=x;i<n;i++)sum=sum*10+a[i]-'0';
		s*=sum;
		if(maxn<s)maxn=s;
		return;
	}
	if(x>=n||y>k)return;
	int sum=0;
	for(int i=x;i<n;i++){
		sum=sum*10+a[i]-'0';
		dfs(i+1,y+1,s*sum);
	}
}
int main(){
    cin>>n>>k;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    a[0]=c;
    for(int i=1;i<n;i++)scanf("%c",&a[i]);
    dfs(0,0,1);
    cout<<maxn;
}