前言
事先声明！博主是不会写高精的屑。因此此题只拿到了开 \(LL\) 的 \(\color{orange}{60}\) 分。
但这并不妨碍我练 \(DP\)。
思路辨析
很容易想到，以前 \(i\) 个数的部分作为一个阶段变量。
有了具体的数量，又很自然的想到将钥匙的个数作为一个变量加进去，也就是 \(j\) 。
诶，好像能行，再看看。
综上，\(dp_{i,j}\) 表示的是前 \(i\) 个数用 \(j\) 个乘号隔开所能得到的最大乘积。
设想一下，当我们知道如上所述的信息时，要怎么通过它得到下一阶段的信息，或它是如何由其它阶段推来的呢?
显然第二种更好推。
已知钥匙的个数，枚举最后一个钥匙所在的位置（这里记为 \(r\) ），可以将前 \(i\) 个数分成两部分。
前半部分是前 \(r\) 个数用 \(j-1\) 个乘号断开所得到的乘积最大值，后半部分则是 \(N\) 个字符中第 \(r+1\) 个字符到第 \(i\) 个字符所组成的数，用两者之积来更新答案。
因此，状态转移方程为
\(dp_{i,j} = \max( dp_{r,j-1} * nu_{r+1,i} , dp_{i,j})\).
注：\(nu_{r+1,i}\)就是 \(N\) 个字符中第 \(r+1\) 个字符到第 \(i\) 个字符所组成的数。
code
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,k,a[45],nu[45][45],dp[45][10];
int main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%1d",&a[i]);//“%1d”每次只读一个数字
for(int i=1;i<=n;i++) nu[i][i]=a[i];
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
nu[i][j]=nu[i][j-1]*10+a[j];
}
}
//这一段是对nu的预处理
for(int i=1;i<=n;i++) dp[i][0]=nu[1][i];//初始化
for(ll i=1;i<=n;i++){
for(int j=1;j<min(i,k+1);j++){//i个数最多只能放i-1个乘号，所以和k+1取min
for(int r=1;r<i;r++){
dp[i][j]=max(dp[r][j-1]*nu[r+1][i],dp[i][j]);
}
}
}
cout<<dp[n][k]<<endl;
return 0;
}
summary
对状态的描述好像有进步！继续加油！
大抵是 \(dp\)百道第三题吧。
↑是的，这是一位摆烂了一学期的屑
标签：NOIP2000,P1018,45,个数,dp,include,个字符,乘积 From： https://www.cnblogs.com/lzyan-blog/p/17008886.html