区间DP学习篇（整数拆分 + 最优三角剖分）

题目链接

整数划分（四）

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

输入

第一行是一个整数T，表示有T组测试数据
接下来T行，每行有两个正整数 n，m ( 1<= n < 10^19, 0 < m <= n的位数)；

输出

输出每组测试样例结果为一个整数占一行

样例输入

1
2
3
2
111 2
1111 2

样例输出

1
2
11
121

这道题给出的思路是这样 ： 理用dp[i][j]表示从1-i区间内用j个乘号的最大值，巧妙地将问题中两个条件同时简化（区间长度，乘号数量）从而实现子问题建立，需要处理num[i][j]数组保存区间i-j的数便于遍历时利用。难就难在动归思想还没掌握熟练，感觉还是积累得太少，状态转移方程 ： dp[i][j] = max(dp[i][j], dp[k][j-1]*num[k+1][i])

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
long long dp[25][25];
char a[25];
long long num[25][25];
int main()
{
int m;
int t;
scanf("%d",&t);
while(t --)
{
scanf("%s%d",a,&m);
memset(dp, 0, sizeof(dp));
int n = strlen(a);
for(int i = 0; i < n; i ++)
{
num[i+1][i+1] = (a[i] - '0');
for(int j = i + 1; j < n; j ++)
num[i+1][j+1] = num[i+1][j] * 10 + (a[j] - '0');
}
for(int i = 1; i <= n; i ++)
dp[i][0] = num[1][i];
for(int j = 1; j < m; j ++)
for(int i = j + 1; i <= n; i ++)
for(int k = j; k < i; k ++)
dp[i][j] = max(dp[i][j], dp[k][j-1]*num[k+1][i]);
printf("%lldn",dp[n][m-1]);
}
return 0;
}

凸多边形三角划分问题

Problem Description

给定一个具有N(N<=50)个顶点(从1到N编号)的凸多边形，每个顶点的权值已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权值的乘积之和最小。

Input

第一行为顶点数N，第二行为N个顶点（从1到N）的权值。

Output

乘积之和的最小值。题目保证结果在int范围内。

Sample Input

5

1 6 4 2 1

5

121 122 123 245 231

Sample Output

34

12214884

【思路】

用dp[i][j]表示从顶点i到顶点j的凸多边形三角剖分后所得到的最大乘积。

那么可以写出状态转移方程，并通过枚举分割点来转移。

1
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])

很神奇地把问题转化成了若干个子问题，且符合动态规划三个条件

解决所有动归问题的关键，就在于寻找最优子方案，然后很容易地能写出状态转移方程啊！！！

如何寻求最优子方案？—> 个人感觉就是把所有限制条件（如序列长度，乘号数量之类的给定变量）通过dp数组进行约束，从而实现子问题的转化，转化过程中需要注意无后效性，最优策略，讲到底如何把大问题拆分成小问题，是一个思维习惯问题，多想想！！！

代码就不贴了，找不到题，思路有了一切很easy。。。

最后

以上就是直率小猫咪最近收集整理的关于区间DP学习篇（整数拆分 + 最优三角剖分）的全部内容，更多相关区间DP学习篇（整数拆分内容请搜索靠谱客的其他文章。