NOIP 2000普及組 乘積最大 詳解

經典DP題，f[i][j] 表示在前i個數字中插入j個乘号時的最大乘積，num[i][j]表示從第i個字元到第j個字元之間的數字，i從0開始

狀态轉移方程：f[i][j]=max(f[k][j-1]*num[k][i-1]),1<=k

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
using namespace std;

char str[];
long long num[][],f[][];
int n,k,lenstr;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>str;
    lenstr=strlen(str);
    for(int i=;i<lenstr;i++)
    {
        num[i][i]=str[i]-'0';
        for(int j=i+;j<lenstr;j++)
            num[i][j]=num[i][j-]*+str[j]-'0';
    }
    for(int i=;i<=lenstr;i++)
        f[i][]=num[][i-];
    for(int i=;i<=lenstr;i++)
        for(int j=;j<=i-&&j<=k;j++)
            for(int k1=;k1<i;k1++)
                if(k1>j-)
                    f[i][j]=max(f[i][j],f[k1][j-]*num[k1][i-]);
    cout<<f[lenstr][k]<<endl;
    return ;
}