看着这么眼熟,遇见洛谷原题了。

这是一道区间动规题,但是,因为我太弱了,所以百般尝试深搜((((好~~难~啊！！

因为这题的样例如此的水,我们不用剪枝不用记忆化不用高精度也能AC(喜

思路:

跟着样例来

4 2
1231

62

乘号可以放在1左边、一和二之间、二和三之间、三和一之间、一右边。算式为:

• *1 * 231(舍,乘号在1前面,还有一个乘号在哪都是0)
• 1 * 2 * 31(=62)
• 1 * 23 * 1(=23)
• 1 * 231 *(舍)
• 12 * 3 * 1(=36)
• 12 * 31 *(舍)
• 123 * 1 *(舍)
• 1231**(舍)

所以为62。

三个递归变量,step是当前第几个乘号,mul为现在的乘积,last来一个当前到了哪一位,枚举每一个可以放乘号的位置,再深搜下去。如果乘号用完,打擂台存答案,返回。

代码:

#include <iostream>
using namespace std;

int n,k;
int maxn = 0;//最大乘积
int a[41];

void dfs(int step,int mul,int last)//step是当前第几个乘号,mul为现在的乘积,last来一个当前到了哪一位
{
    if(step > k)//乘号用完了
    {
	    int num = 0;//注意为0不是1
	    for(int i = last + 1;i <= n;i++)//将剩下的没乘的乘上
	    {
			num = num * 10 + a[i];//因为是字符串,所以要用一个变量将ta提出来,即×10+a[i]
		}
		maxn = max(maxn,mul * num);//打擂台
	    return;//返回◀
    }
    
    for(int i = last + 1;i <= n - k + step;i++)//从last+1开始
    {
        int num = 0;
        for(int j = last + 1;j <= i;j++)
        {
			num = num * 10 + a[j];//同上
		}
        dfs(step + 1,num * mul,i);//下一个乘号,下一个乘积,last为i
    }
    return;
}

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
    {
    	char c;
        cin >> c;
        a[i] = c - '0';//用数组储存
    }
    dfs(1,1,0);
    cout << maxn;
}

因为我是蒟蒻,正解弄不粗来...

/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 100 + 10;
const int INF = 0x3f3f3f3f;
struct node
{
	int a[N];
	node()
	{
		memset(a,0,sizeof(a));
	}
	void operator = (const node &s)
	{
		memcpy(a,s.a,sizeof(s.a));
	}
	node operator + (const int &s)
	{
		node t;
		t.a[0] += s;
		for(int i = 0 ; i < 50 ; i++)
		{
			t.a[i] += a[i];
			t.a[i+1] += t.a[i]/10;
			t.a[i] %= 10;
		}
		return t;
	}
	node operator + (const node &s)
	{
		node t;
		for(int i = 0 ; i <= 50 ; i++)
		{
			t.a[i] += a[i] + s.a[i];
			t.a[i+1] += t.a[i]/10;
			t.a[i] %= 10;
		}
		return t;
	}
	node operator * (const node &s)
	{
		node t;
		for(int i = 0 ; i < 50 ; i++)
			for(int j = 0 ; j < 50 ; j++)
			{
				t.a[i+j] += a[i] * s.a[j];
				t.a[i+j+1] += t.a[i+j]/10;
				t.a[i+j] %= 10;
			}
			return t;
	}
	node operator << (const int &s)
	{
		node t;
		for(int i = 50 ; i >= 0 ; i--)
			t.a[i+s] = a[i];
		return t;
	}
	bool operator < (const node &s)
	{
		for(int i = 50 ; i >= 0 ; i--)
			{
				if(a[i] < s.a[i])	return true;
				else if(a[i] > s.a[i])	return false;
			}
			return false;
	}
	void print()
	{
		int len = N - 1;
		while(a[len] == 0 && len > 0)
			len--;
		for(int i = len ; i >= 0 ; i--)
			cout << a[i];
		cout << endl;
	}
};
int n , k;
char num[100];
node x , sum[N][N] , dp[N][N];
int main()
{
	cin >> n >> k;
	cin >> num;
	for(int i = 0 ; i < n ; i++)
		x.a[i] = num[i] - '0';
	for(int i = 0 ; i < n ; i++)
		for(int j = i ; j < n ; j++)
			if(i == j)
				sum[i][j].a[0] = x.a[j];
			else
				sum[i][j] = (sum[i][j-1] << 1) + x.a[j];

	for(int i = 0 ; i <= k ; i++)
		for(int j = 0 ; j <= n ; j++)
			dp[j][i].a[0] = 1;

	for(int i = 0 ; i < n ; i++)
		dp[i][0] = sum[0][i];

	for(int l = 1 ; l <= k ; l++)
		for(int i = l ; i < n ; i++)
			for(int j = l-1 ; j < i ; j++)
				if(dp[i][l] < dp[j][l-1] * sum[j+1][i])
					dp[i][l] = dp[j][l-1] * sum[j+1][i];

	dp[n-1][k].print();
    return 0;
}
```c