NC16751. [NOIP2000]乘积最大
描述
输入描述
第一行共有2个自然数N,K(6 ≤ N ≤ 40,1 ≤ K ≤ 6)
第二行是一个长度为N的数字串。
输出描述
输出所求得的最大乘积(一个自然数)。
示例1
输入:
4 2 1231
输出:
62
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 520K, 提交时间: 2018-09-16 11:59:29
#include<bits/stdc++.h> using namespace std; long long n,g,w,f[12][12],a[12][12]; int main() { cin>>n>>g>>w; for(int i=n;i>=1;i--) { a[i][i]=w%10; w/=10; } for(int i=2;i<=n;i++) for(int j=i-1;j>=1;j--) a[j][i]=a[j][i-1]*10+a[i][i]; for(int i=1;i<=n;i++) f[i][0]=a[1][i];//a[1][i] for(int k=1;k<=g;k++) for(int i=k+1;i<=n;i++) for(int j=k;j<i;j++) f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]); cout<<f[n][g]<<endl; }
C(clang 3.9) 解法, 执行用时: 3ms, 内存消耗: 364K, 提交时间: 2019-08-04 12:14:52
#include "stdio.h" double f[45][45],num[45][45]; char s[45]; int main() { int n,m,k,i,j; scanf("%d%d",&n,&m); scanf("%s",s+1); for(i=1;i<=n;i++) for(j=i;j<=n;j++) num[i][j]=num[i][j-1]*10+s[j]-'0'; for(i=1;i<=n;i++)f[i][0]=num[1][i]; for(i=2;i<=n;i++) for(j=1;j<=m;j++) for(k=j;k<=i-1;k++) if(f[k][j-1]*num[k+1][i]>f[i][j])f[i][j]=f[k][j-1]*num[k+1][i]; printf("%.0lf",f[n][m]); return 0; }
Python3 解法, 执行用时: 40ms, 内存消耗: 6968K, 提交时间: 2021-09-13 17:54:57
n,m=map(int,input().split(' ')) s=input() dp=[[0]*(m+1) for i in range(n)]#n+1行m+1列 for i in range(0,n): dp[i][0]=int(s[0:i+1]) for i in range(n): for j in range(1,m+1): for k in range(i): dp[i][j]=max(dp[i][j],dp[k][j-1]*int(s[k+1:i+1])) print(dp[n-1][m])