划分型DP

1.乘积最大（NOIP2000）
http://codevs.cn/problem/1017/

方程：

f[i][j] = max{f[k][j-1] + to_num(k+1~i)} (1 <= k < i)
to_num(low~high)表示将第low位到第high位转化成一个数字

代码：

#include<bits/stdc++.h>
#define MAXN 50
#define MAXK 10
using namespace std;

int n, k;
char str[MAXN];
long long f[MAXN][MAXK];

long long to_num(int low, int high)
{
    long long ret = 0;
    for (int i = low; i <= high; i++)
        ret = ret * 10 + (str[i - 1] - '0');
    return ret;
}

int main()
{
    scanf("%d%d", &n, &k);
    scanf("%s", str);
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
        f[i][0] = to_num(1, i);
    for (int j = 1; j <= k; j++)
        for (int i = 1; i <= n; i++)
            for (int l = j; l < i; l++)
                f[i][j] = max(f[i][j], f[l][j - 1] * to_num(l + 1, i));
    printf("%dn", f[n][k]);
    return 0;
}

2.数的划分（NOIP2001提高组）
http://codevs.cn/problem/1039/

方程：

f[i][j] = f[i - j][j] + f[i - 1][j - 1] (1 <= j <= min{i, k})

代码：

#include<bits/stdc++.h>
#define MAXN 300
#define MAXK 10

using namespace std;

int n, k;
int f[MAXN][MAXK];

int main()
{
    scanf("%d%d", &n, &k);
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= min(i, k); j++)
            f[i][j] = f[i - j][j] + f[i - 1][j - 1];
    printf("%d", f[n][k]);
    return 0;
}

3.统计单词个数（NOIP2001提高组）
http://codevs.cn/problem/1040/

方程：

f[i][k]=max(f[i][k], f[j][k-1]+word_cnt(j+1~i)）
f[i][k]表示把前i个字母分成k个部分的最优解
word_cnt(low~high)表示从low到high位置的最多的单词数

PS：预处理很麻烦。

代码：

#include<bits/stdc++.h>
#define MAX_LEN 300
#define MAX_K 50
#define MAX_S 10

using namespace std;

int n, p, k, s;
char str[MAX_LEN];//字母串 
char word[MAX_S][MAX_LEN];//字典 
char temp[MAX_LEN];//临时字符串 
int word_len[MAX_S];//word_len[i]-word[i]的长度 
int strt[MAX_LEN];//temp[i]-以str[i]开头的单词长度 
int word_cnt[MAX_LEN][MAX_LEN];//word_cnt[i][j]-str[i]~str[j]之间最多的单词数
int f[MAX_LEN][MAX_K];//f[i][j]-到str[i]为止分成j份最多的单词数

void get_substr(int start, int length)
{
    for (int i = 0; i < MAX_LEN; i++)
        temp[i] = '';
    for (int i = 0; i < length; i++)
        temp[i] = str[start + i];
}

void work()
{
    scanf("%d%d", &p, &k);
    for (int i = 0; i < p; i++)
        scanf("%s", &str[1 + i * 20]);
    p *= 20;
    scanf("%d", &s);
    for (int i = 0; i < s; i++)
    {
        scanf("%s", word[i]);
        word_len[i] = strlen(word[i]);
    }
    memset(strt, 0, sizeof(strt));
    for (int i = 1; i <= p; i++)
        for (int j = 0; j < s; j++)
        {
            get_substr(i, word_len[j]);
            if ((strcmp(word[j], temp) == 0) && ((strt[i] == 0) || (strt[i] > word_len[j])))
                strt[i] = word_len[j];
        }
    memset(word_cnt, 0, sizeof(word_cnt));
    for (int i = 1; i <= p; i++)
        for (int j = i; j <= p; j++)
        {
            word_cnt[i][j] = word_cnt[i][j - 1];
            for (int l = i; l <= j; l++)
                if (strt[l] == j - l + 1) 
                    word_cnt[i][j] += 1;
        }
    memset(f, 0, sizeof(f));
    for (int j = 1; j <= k; j++)
        for (int i = j; i <= p; i++)
            for (int l = j - 1; l < i; l++)
                f[i][j] = max(f[i][j], f[l][j - 1] + word_cnt[l + 1][i]);
    printf("%dn", f[p][k]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        work(); 
    return 0;
}

最后

以上就是温婉指甲油为你收集整理的划分型DP的全部内容，希望文章能够帮你解决划分型DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。