Comment

betterElon: 2024-12-22 11:51:26

//求助，不知道哪里错了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50, K  =10 ;
long long int f[N][K];//dp，f[i][j]表示在前i位字符中放入j个乘号能够获得的最大的乘积;
int mysize,k;
int a[N];
long long int get(int l,int r){
    long long int res=0;
    for(int i=l;i<=r;i++){
        res=res*10+a[i];
    }
    return res;
}
int main()
{
    int M; cin>>M;
    while (M -- ){
        for(int i=0;i<N;i++){
            for(int j=0;j<K;j++){
                f[i][j]=0;
            }
        }
        int n;//num
        int m;
        cin>>mysize>>m>>n;
        for(int i=mysize;i>=1;i--){
            f[i][0]=n;//初始化f【i】【0】
            a[i]=n%10;
            n=n/10;
            
        }
        
       
        for(int i=1; i<=mysize ; i++){
            for(int j=1; j<=i-1; j++){
                for(int k=j;k<=i-1;k++){
                     f[i][j] = max(f[i][j], f[k][j - 1] * get(k + 1, i));

                }
            }
        }
        
        
        
        cout<<f[mysize][m]<<endl;
    }
}

hanser414627925: 2024-05-29 18:31:42

#include<iostream>		用long long 
using namespace std;
int main()
{
	int m, n, k;//长度为n的数字串，使用k个乘号
	cin >> m;
	long long  max[40][7], data[40][40];
	//max[i][j]表示从第0个数字到第i个数字中插入j个乘号时所得到的最大值，
	//data[i][j]表示截取第i个数字到第j个数字所得到的数值。
	//memset(max, 0, sizeof(max));
	for (int i = 0; i < m; i++)
	{
		for (int i = 0; i < 40; i++)
			for (int j = 0; j < 7; j++)
				max[i][j] = 0;
		cin >> n;
		cin >> k;
		char* a = new char[n];
		for (int j = 0; j < n; j++)
			cin >> a[j];
		for (int j = 0; j < n; j++)	//将字符串转换为data
		{
			long long temp = 0;
			for (int t = j; t < n; t++)
			{
				temp = temp * 10 + a[t] - '0';
				data[j][t] = temp;
			}
		}
		for (int j = 0; j < n; j++)	//初始化max[j][0]即用0个乘号时的结果	
			max[j][0] = data[0][j];
		for (int j = 0; j < n; j++)
			for (int w = 1; w <= k && w <= j; w++)
				for (int t = 0; t < j; t++)//
					max[j][w] = (max[t][w - 1] * data[t + 1][j] > max[j][w] ?
						max[t][w - 1] * data[t + 1][j] : max[j][w]);
		cout << max[n - 1][k] << endl;
	}
	return 0;
}

222026: 2022-11-13 15:56:20

为什么我用memset初始化dp数组 它会报编译错误啊 我改成循环做就对了。。。。。

61520216: 2022-05-03 22:49:52

一开始中间卡了一下, 没有想到动态规划的解法,但也是从最优解出发想出了一种删除乘号的方法. 例如321044105可以先初始化为
3*2*1*0*4*4*1*0*5
然后依次计算相邻两项组合后的值与相乘的值的比, 比如
32/(3*2) = 5.3
21/(2*1) = 10.5
10/0 = inf
然后删除比值最大的一项所对应的乘号, 比如一开始肯定是要删除0前面的乘号, 变成
3*2*10*4*4*10*5
依次这样下去就可以得到最后的结果

因为这样下来, 每次上一步连乘都是是最大值, 删除的乘号所对应的放大比例也是最大值, 因此每删一个乘号的结果也是最大值
时间复杂度为O(N(N-K))
可以用链表实现

0937_0938: 2022-03-02 16:10:33

真的无语，n显然没到40，直接记忆化搜索就完事了，我还以为会超时出错啥的。。。

klhsag: 2021-12-23 14:58:37

所以N实际上只有大概最多20？

copker: 2021-12-20 22:55:27

我是煞笔，真给写了个高精度。。。结果点进来看告诉我longlong就成了。。。

copker: 2021-12-20 22:55:01

#include <iostream>
#include <string>
using namespace std;



class NUM {
public:
    int num[100];
    int len=0;

    NUM() {
        for (int i = 0;i < 100;i++) num[i] = 0;
    }

    void init(int a[], int l, int r) {
        int p = l;
        while ((a[p] == 0) && (l <= r)) {
            p++;
        }
        for (int i = p;i < r + 1;i++) {
            num[r - i] = a[i];
        }
        len = r - p + 1;
    }

    NUM operator*(const NUM& n) {
        NUM ans;
        if (this->len == 0 || n.len == 0) return ans;
        int c=0;
        for (int i = 0;i < this->len;i++) {
            c = 0;
            int temp[100];
            for (int j = 0;j < n.len;j++) {
                temp[j] = c+n.num[j] * this->num[i];
                c = temp[j] / 10;
                temp[j] = temp[j] % 10;
            }
            int l=n.len;
            if (c != 0) {
                temp[n.len] = c;
                l++;
            }
            c = 0;
            for (int j = 0;j < l;j++) {
                ans.num[j+i] = c + ans.num[j+i] + temp[j];
                c = ans.num[j+i] / 10;
                ans.num[j+i] = ans.num[j+i] % 10;
            }
            if (c != 0) ans.num[n.len + i] = c;
        }
        ans.len = this->len + n.len-1;
        if (ans.num[ans.len] != 0) ans.len++;
        return ans;
    }

    NUM operator+(const NUM& n) {
        NUM ans;
        int c = 0;
        int len;
        if (n.len > this->len) len = n.len; else len = this->len;
        for (int i = 0;i < len;i++) {
            ans.num[i] = n.num[i] + this->num[i];
            c = ans.num[i] / 10;
            ans.num[i] = ans.num[i] % 10;
        }
        if (c != 0) {
            ans.num[len + 1] = 1;
            ans.len = len + 1;
        }
    }

    bool operator>(const NUM& n) {
        if (this->len > n.len) return true;
        if (this->len < n.len) return false;
        for (int i = this->len - 1;i >= 0;i--) {
            if (this->num[i] > n.num[i]) return true;
            if (this->num[i] < n.num[i]) return false;
        }
        return false;
    }

    friend ostream& operator<<(ostream& output,
        const NUM& n)
    {
        if (n.len == 0) output << 0;
        for (int i = n.len-1;i >=0;i--) output << n.num[i];
        return output;
    }

    void copy(NUM n) {
        this->len = n.len;
        for (int i = 0;i < len;i++) this->num[i] = n.num[i];
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int len = s.length();
    int a[100];
    NUM* p[100][10];
    for (int i = 0;i < len;i++) {
        a[i] = s[i] - 48;
    }
    for (int i = 0;i < len;i++) {
        p[i][0] = new NUM();
        p[i][0]->init(a,0,i);
    }
    for (int i = 0;i < len;i++) {
        for (int j = 1;j < k+1;j++) {
            p[i][j] = new NUM();
            for (int k = 0;k < i;k++) {
                NUM temp;
                temp.init(a, k+1,i);
                temp = *p[k][j - 1] * temp;
                if (temp > *p[i][j]) 
                    p[i][j]->copy(temp);
            }
        }
    }
    cout << *p[n-1][k] << endl;
}

int main() {
    int m;
    cin >> m;
    for (int i = 0;i < m;i++) {
        solve();
    }
}

214801: 2021-12-09 00:52:01

有没有人想过，其实这样拆分，每次从最靠近9的那一位分割即可，例如实例的321044105，在5，4，4，3进行切割，3*210*4*410*5即
可，而且可以证明，因为拆开表明损失10的倍数倍，就算拆开的是0，只有乘10才能恢复，为了更好的贴近原本的数字（也就是更大），
乘9当然比乘8好，以此类推，损失越小越好。在实例中，410的选择就是因为切割0损失10，切割10损失9，切割410损失6

214801: 2021-12-09 00:51:33

有没有人想过，其实这样拆分，每次从最靠近9的那一位分割即可，例如实例的321044105，在5，4，4，3进行切割，3*210*4*410*5即可，而且可以证明，因为拆开表明损失10的倍数倍，就算拆开的是0，只有乘10才能恢复，为了更好的贴近原本的数字（也就是更大），乘9当然比乘8好，以此类推，损失越小越好。在实例中，410的选择就是因为切割0损失10，切割10损失9，切割410损失6

wuboxin: 2021-06-08 21:04:02

注意:不识别pow函数

Undefined: 2021-05-01 17:22:38

记忆化搜索，可以省略一些不必要的节点计算。
记得每次询问重置缓存。

// author: lee
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 22, K = 22;
int m, n, k;
// 各位数字
int srcNum[N];
// 缓存
long long val_mem[N][N];

// 提取第st位到第ed位数字
long long getNum(int st, int ed){
	long long val = 0;
	for (int i = st; i <= ed; i++){
		val = val * 10 + srcNum[i];
	}
	return val;
}

// 第0个数到第i个数中插入k个乘号得到的最大值
long long getVal(int i, int k){
	// 若有缓存则直接返回
	if (val_mem[i][k]){
		return val_mem[i][k];
	}

	// 插0个乘号，就是直接返回那段数字
	if (k == 0){
		return val_mem[i][k] = getNum(0, i);
	}

	long long ans = 0;
	// 状态转移，乘号数k单调递减，递归
	for (int i2 = k - 1; i2 < i; i2++){
		ans = max(
			ans, 
			getVal(i2, k - 1) * getNum(i2 + 1, i)
		);
	}
	return val_mem[i][k] = ans;
}


int main()
{
	// 测试getNum()函数用
	// for (int i = 0; i < 5; i++)
	// 	scanf("%d", &srcNum[i]);

	// for (int i = 0; i < 3; i++){
	// 	int st, ed;
	// 	scanf("%d%d", &st, &ed);
	// 	printf("%d", getNum(st, ed));
	// }

	// input
	scanf("%d", &m);
	for (int i = 0; i < m; i++){
		scanf("%d%d", &n, &k);
		
		// each input
		char temp[50];
		scanf("%s", temp);
		for (int j = 0; j < n; j++){
			srcNum[j] = temp[j] - '0';
		}

		// init val_mem
		memset(val_mem, 0, sizeof(val_mem));

		// calcualte answer
		long long ans = getVal(n - 1, k);

		// output
		printf("%lld\n", ans);
	}

	return 0;
}

09019105王璟: 2021-05-01 01:18:04

我好了

09019105王璟: 2021-05-01 00:54:47

求助，为什么老runtime error,不懂

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s; 
long long f[6][41] = {0}, n, k;//f[i][j]为使用i个乘号时s(0-j)能产生的最大积
long long cs(int ks, int js)//计算s（ks,js）段的数值
{
	long long sum = 0, t = 1;
	for (int i = js; i >= ks; i--) { sum = sum + (s[i] - '0')*t, t = t * 10; }
	return sum;
}
int main()
{
	int times; cin >> times; getchar();  int p = 0;
	while(++p<=times)
	{
	cin >> n >> k >> s; f[41][41] = { 0 };
	for (int i = 0; i < n; i++) { f[0][i] = cs(0, i); }//在没有乘号的情况下最优解总是前i位
	for (int i = 1; i <= k; i++)//乘号数递增
	{
		for (int j = 1; j <= n; j++)//s范围往后增
		{
			for (int h = j; h >= i; h--)
			{
				f[i][j] = max(f[i][j], f[i - 1][h - 1] * cs(h, j));
                   //更小的子问题的最优解f[i - 1][h - 1]已经确定
			}
		}
	}
	cout<<f[k][n - 1]<<endl;//最优解
	};
}

09019310: 2021-04-30 23:39:39

粘贴错位置了orz

09019310: 2021-04-30 21:53:34

/*
 * @Description:
 * @Author: Qi
 * @Date: 2021-04-30 20:11:40
 * @LastEditors: Qi
 * @LastEditTime: 2021-04-30 21:53:08
 */
#include <iostream>

inline long long int max(long long int x, long long int y)
{
  return x > y ? x : y;
}

using namespace std;

int arr2int(int *arr, int l, int r)
{
  int num = 0;
  while (l <= r)
  {
    num *= 10;
    num += arr[l++];
  }
  return num;
}

long long int dp(int N, int *arr, int K)
{
  long long int **dp = new long long int *[N];
  for (int i = 0; i < N; i++)
  {
    dp[i] = new long long int[K + 1];
  }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < K + 1; j++)
      dp[i][j] = 0;
  for (int i = 0; i < N; i++)
  {
    dp[i][0] = arr2int(arr, 0, i);
  }
  for (int i = 0; i < N; i++)
  {
    for (int j = 1; j <= K; j++)
    {
      for (int k = 0; k < i; k++)
      {
        dp[i][j] = max(dp[k][j - 1] * arr2int(arr, k + 1, i), dp[i][j]);
      }
    }
  }
  // cout << "dp[i][j]:" << endl;
  // for (int i = 0; i < N; i++)
  // {
  //   for (int j = 0; j <= K; j++)
  //     cout << dp[i][j] << ' ';
  //   cout << endl;
  // }
  return dp[N - 1][K];
}

int main()
{
  int M;
  cin >> M;
  while (M--)
  {
    int N, K;
    cin >> N >> K;
    int *arr = new int[N];
    int n;
    cin >> n;
    for (int i = N - 1; i >= 0; i--)
    {
      arr[i] = n % 10;
      n /= 10;
    }
    cout << dp(N, arr, K) << endl;
    delete[] arr;
  }
}

fwbbyy: 2021-04-30 20:45:52

感谢一楼大哥，被卡了半天，换成long long int之后过了

_heye_: 2021-03-31 00:13:54

谢谢楼上大哥，我一直memset放错位置了 才一直没发现

huhong: 2020-12-13 20:16:35

别忘了memset dp数组。。

200818倪鹏宇: 2020-09-29 16:25:56

不需要高精度，long long可过