初始状态决定了你的走向

懵逼的 题目

传送至 Codevs

扯淡的 题解

划分dp的主要思路是把序列中的一段接在已经得出结果的一段后面….大概就酱…然后没初始化d[0][]….调了一天(居然能过样例)….

沙茶的 代码

// codevs 1017.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#define LL unsigned long long //既然long long 能过我为什么要用高精?
#define MAXN (40+5)
using namespace std;
int n;
int k;
LL f[MAXN][MAXN];//f[i][j]表示i~j之间的a代表的数
LL d[MAXN][MAXN];//d[i][j]表示前j个字符已分为i份的乘机
string a;
LL zhuan(int, int);
int main()
{
    cin >> n >> k >> a;    
    for (int j = 0; j <= n; j++)
    {
        d[0][j] = 1;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            f[i][j] = zhuan(i, j);
            //d[0][i][j] = f[i][j];
            //cout << i <<" "<< j<<endl;
            //cout << f[i][j]<<endl;
        }
    }
    for (int i = 0; i < n; i++)
    {
        d[0][i] = f[0][i];
    }
    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int ka = j + 1; ka < n; ka++)
            {
                d[i][ka] = max(d[i][ka], d[i - 1][j] * f[j+1 ][ka]);
            }
        }
    }
    cout << d[k][n-1];
    return 0;
}
LL zhuan(int l, int r)
{
    LL re = 0;
    for (int i = l; i <= r; i++)
    {
        re *= 10;
        re += (a[i] - '0');
    }
    return re;
}