HDOJ1421

Posted on

HDOJ1421

又是动态规划的题目，dp方面问题对现阶段的自己还是一个坎，还是要多理解多刷题。

数塔
首先从简单的数塔入手，从第一行开始走，走到最后一行，怎么使经过的值之和最大？

dp问题的核心：找到状态并建立状态转移方程

首先需要建立一个数塔模型，模型中的元素用a(i,j)(j<=i)表示，如第三行第二个元素10用a(3,2)表示。并且我们规定从a(i,j)往下走所能得到的最大值为dp(i,j)。
我们以数塔中任意一个元素a(i,j)为一个状态，根据规则，该元素可以选择向左下方a(i+1,j)或者右下方a(i+1，j+1)移动(最后一行除外)，显然对于处于a(i,j)一定选择{dp(i+1,j),dp(i+1,j+1)}中较大的值，于是我们得到了dp(i,j)的计算公式：dp(i,j)=a(i,j)+max(dp(i+1,j),dp(i+1,j+1))，这就是我们所要找的状态转移方程。很容易就知道该问题的最终答案是dp(1,1)。

接下来介绍三种方法来求解：
1.递归求解

1
2
3
4
5
6
int dp(int i,int j)
{
	if(i!=n)return a[i][j]+=max(dp(i+1,j),dp(i+1,j+1));
	else return 0;
	//n表示最后一行的行数，即为边界
}

分析该算法，会发现效率很低。例如对于上图dp(3,2),dp(4,2),dp(4,3)将会被重复计算，但是这部分的结果一样，却被重复计算，我们就要设法使这部分不被重复，很显然，要使他不重复，那就在第一次计算的时候把结果记录下来，下次遇到的时候直接使用，就避免了重复计算。

2.根据算法1的分析，我们得到了带记忆功能的算法。

1
2
3
4
5
6
7
int dp(int i,int j)
{
//第一行就是所说的记忆功能，如果dp>=0,就表明它已经被计算过了，可以直接使用，
//所以在函数之前要将dp的值全赋值成-1，表示dp都未被计算过memset(dp,-1,sizeof(dp))
	if(dp(i,j)>=0)return dp(i,j);
	else return dp[i][j]=a[i][j]+max(dp(i+1,j),dp(i+1,j+1));
}

这里写图片描述这里写图片描述

从图中很直观的看出记忆功能的算法能直接利用计算过的结果。

3.递推算法
算法3改变了思路，前两种都是自顶向下计算，算法3则选择从下向上计算，而且规定一下是从左下角向顶角计算。

1
2
3
4
5
for(int i=n;i>=1;i--)
	for(int j=1;j<=i;j++)
		dp[i][j]=a[i][j]+max(a[i-1][j],a[i-1][j+1]);
//仔细分析甚至连dp数组都可以不用
		a[i][j]+=max(a[i-1][j],a[i-1][j+1]);

下面给出数塔问题ACM2084的完整代码，这里选择算法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#define MAXN 105
int a[MAXN][MAXN];
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= i; j++)
				cin >> a[i][j];
		for (int i = n - 1; i >= 1; i--)
			for (int j = 1; j <= i; j++)
				a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
		cout << a[1][1] << endl;
	}
	return 0;
}

接下来分析一下开头的ACM1421
首先必须承认渣渣的我这道题想了很久，也是借鉴了别人的思路。

先申明用a[n]来存储输入的数据，用dp[i][j]表示从i个数中取j对时的最小值，例如dp[3][1]表示从3个数取1对的最小疲劳度(当然三个数的时候也只能取一对)

我想从题意中应该很容易想到给数组a进行排序

1
sort(a,a+n);

我们先从简单的找找规律：
当只有两个数的时候，结果显然等于(a[2]-a[1])*(a[2]-a[1]),根据前面的定义我们把结果记作dp[2][1];
当有三个数，要么a[1]和a[2],要么a[2]和a[3]组合，我们取两个组合的最小值,因此：

1
dp[3][1]=min(dp[2][1],(a[3]-a[2])*(a[3]-a[2]));

我们接着在推一个当四个数的时候，此时我们可以选取一对或者两对,
此时选取一对可以分成两类：

1
2
1.不包括第四个数时，dp[4][1]=dp[3][1];
2.包括第四个数时，dp[4][1]=(a[4]-a[3])*(a[4]-a[3]);

选取两对：

1
dp[4][2]=dp[2][1]+(a[4]-a[3])*(a[4]-a[3]);

不知道你们发现什么没(如果还没有,可以在推一两组找找规律）

1
2
3
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);
//其实这就是我们要找的状态转移方程
//假设要找i个元素中j对的最小值:要么从前i-1个元素中找j对；要么从前i-2个元素中找j-1对+a[i]-a[i-1])*(a[i]-a[i-1]；

既然找到了状态转移方程，我们就根据题意进行一些细节的处理

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
#include<iostream>
#include<algorithm>
#define MAXN 2050
int dp[MAXN][MAXN];
int a[MAXN];
using namespace std;
int main()
{
	int n, k;
	while (cin >> n >> k)
	{
		
		for (int i = 1; i <=n; i++)
			cin >> a[i];
		sort(a+1, a + n+1);
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= k; j++)
				dp[i][j] = 268435456; 
		for (int i = 2; i <= n; i++)
			for (int j = 1; 2*j<= i ; j++)
				dp[i][j] = min(dp[i - 2][j - 1] + (a[i] - a[i - 1])*(a[i] - a[i - 1]), dp[i - 1][j]);
		cout << dp[n][k]<<endl;
	}
	return 0;
}