学习笔记_codevs1017[划分DP] 调了一天发现没初始化

初始状态决定了你的走向

懵逼的 题目

传送至 Codevs

扯淡的 题解

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

沙茶的 代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 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;
}