---

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可过

Post Your Comment