简单的搜索1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include<cstdio>
#include<iostream>
using namespace std;int k;
int s[1999][1999],a[9999];int tot=-999;int m,n;
int dfs(int x,int k,int ans,int j){
if(n-x<k)return 1;
if(k==0)
{
tot= max(tot,ans*s[x][n]);
//printf("%d ",ans);
return 1;
}
dfs(x+1,k,ans,j);
dfs(x+1,k-1,ans*(s[j][x]),x+1);
}
char h[9999];
int maxn=-9999;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
cin>>h[i]；
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
s[i][j]=s[i][j-1]*10+h[j]-'0';
}
dfs(1,k,1,1);
printf("%d",tot);
}
dp
状态转移方程为dp[i][j]=max(dp[i][j],dp[q][j-1]*s[q+1][i]);
枚举前i个数，用了j个乘号
枚举q为前一个乘号的位置
i位置由前一个乘号即q位置转移过来的1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include<cstdio>
#include<iostream>
using namespace std;int k;
int s[1999][1999],a[9999],dp[999][99];int m,n;
char h[9999];
int maxn=-9999;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
s[i][j]=s[i][j-1]*10+h[j]-'0';
}
for(int i=1;i<=n;i++){
dp[i][0]=s[1][i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
for(int q=j;q<i;q++){
dp[i][j]=max(dp[i][j],dp[q][j-1]*s[q+1][i]);
}
printf("%d",dp[n][k]);
}