很明显,这道题用动归

信息学奥赛一本通能过,但洛谷WA

//信息学奥赛一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1275 
#include<bits/stdc++.h>
using namespace std;

int n,k,dp[50][50],b[50][50];
char a[10100];

int main()
{
	scanf("%d%d%s",&n,&k,&a);
	for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)if(i<j)b[i][j]=b[i][j-1]*10+a[j-1]-'0';else b[i][j]=a[j-1]-'0';
	for(int i=1;i<=n;++i)dp[i][0]=b[1][i];
	for(int i=1;i<=k;++i)for(int j=i+1;j<=n;++j)for(int t=i;t<j;++t)dp[j][i]=max(dp[j][i],dp[t][i-1]*b[t+1][j]);
	printf("%d",dp[n][k]);
	return 0;
}

but 这数据,暴力的话,时间复杂度应该......!

没必要看了,你只需要知道WA了

#include<bits/stdc++.h>
#include<queue>
using namespace std;

#define N 100005

char c[50];
long long n,k;

long long number(long long l,long long r)
{
	--l;
	--r;
	long long x=0;
	for(int i=l;i<=r;++i)x=x*10+c[i]-'0';
	return x;
}

long long f(long long i,long long k,long long s)
{
	if(k==0)return s*number(i,n);
	long long ret=1;
	for(int j=i;j<=n-k;++j)ret=max(ret,f(j+1,k-1,s*number(i,j)));
	return ret;
}

int main()
{
    scanf("%lld%lld%s",&n,&k,c);
    printf("%lld",f(1,k,1));
	return 0;
} 

但暴力总感觉可以,so,谁能写个暴力看看?