week10作业——动态规划（一）

A-签到题

题目要求

东东在玩游戏“Game23”。
在一开始他有一个数字n，他的目标是把它转换成m，在每一步操作中，他可以将n乘以2或乘以3，他可以进行任意次操作。输出将n转换成m的操作次数，如果转换不了输出-1。
Input
输入的唯一一行包括两个整数n和m（1<=n<=m<=5*10^8).
Output
输出从n转换到m的操作次数，否则输出-1.

求解思路

采用递归的方式进行乘2，乘3排列，递归终止条件为找到m,或者大于m。
通过p记录操作的次数，jud记录是否找到m。

void func(int num,int p)
{
	if (num > m)
	{
		return;
	}
	if (num == m)
	{
		jud = true;
		k = p;
		return;
	}
	func(num * 2,p+1);
	func(num * 3,p+1);
}

1. 最优解性质：
   n 转成 m

2. 动态规划方程

3. 自底向上（递推）或带备忘的自顶向下（记忆化搜索）方式计算最优值

4. 构造最优解

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

int n, m;
bool jud;
int k;
void func(int num,int p)
{
	if (num > m)
	{
		return;
	}
	if (num == m)
	{
		jud = true;
		k = p;
		return;
	}
	func(num * 2,p+1);
	func(num * 3,p+1);
}

int main()
{
	cin >> n >> m;
	jud = false;
	k = 0;
	func(n,k);
	if (jud)
	{
		cout << k ;
	}
	else
	{
		cout << -1 ;
	}
}

B - LIS & LCS

题目要求

LIS:最长递增序列
LCS:最长公有序列

东东有两个序列A和B。
他想要知道序列A的LIS和序列AB的LCS的长度。
注意，LIS为严格递增的，即a1<a2<…<ak(ai<=1,000,000,000)。
Input
第一行两个数n，m（1<=n<=5,000,1<=m<=5,000）
第二行n个数，表示序列A
第三行m个数，表示序列B
Output
输出一行数据ans1和ans2，分别代表序列A的LIS和序列AB的LCS的长度

Simple Input
5 5
1 3 2 5 4
2 4 3 1 5
Simple Output
3 2

求解思路

LIS:

1. 最优解性质：
   最长上升子序列
2. 动态规划方程
   初始化 f1=1
   转移方程 fi = max{ fj | j < i && Aj < Ai } + 1
3. 自底向上（递推）或带备忘的自顶向下（记忆化搜索）方式计算最优值
   采用递推方式：
   通过两重循环更新f数组的值：
   当 j < i && Aj < Ai 时，Ai可以至少为Aj + 1，扫描A2~Ai，满足 j < i && Aj < Ai 最大的Aj + 1 即为 Ai 的值。

for(int i=2;i<=n;i++)
		for (int j = 1; j < i; j++)
		{
			if (a[j] < a[i])
			{
				if (f[j] + 1 > f[i])
				{
					f[i] = f[j] + 1;
				}
			}
		}

4. 构造最优解
   最优解为 max { f [ i ] , i……n }

ll mx = 0;
	for (int i = 1; i <= n; i++)
	{
		if (f[i] > mx)
		{
			mx = f[i];
		}
	}
	return mx;

5. 时间复杂度 O(n^2)

LCS:

1. 最优解性质：
   最长公共子序列
2. 动态规划方程
   初始化 f[1][0]= f[0][1]= f[0][0]=0
   转移方程
   当 Ai==Bj时，f[i][j] = f[i-1][j-1]+ 1,否则，f[i][j] = max{ f[i-1][j],f[i][j-1]}
3. 自底向上（递推）或带备忘的自顶向下（记忆化搜索）方式计算最优值
   采用递推方式：
   通过两重循环更新f数组的值：

for(int i=1;i<=n;i++)
		for (int j = 1; j <= m; j++)
		{
			if (a[i] == b[j])
			{
				g[i][j] = g[i - 1][j - 1] + 1;
			}
			else
			{
				g[i][j] = max(g[i - 1][j], g[i][j - 1]);
			}
		}

4. 构造最优解
   最优解为 f[n][m]

5. 时间复杂度 O(nm)

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
typedef long long ll;
using namespace std;

ll a[5005];
ll b[5005];
ll f[5005];
ll g[5005][5005];
ll n, m;

ll LIS()
{
	f[1] = 1;
	for (int i = 2; i < 5005; i++)
	{
		f[i] = 1;
	}
	for(int i=2;i<=n;i++)
		for (int j = 1; j < i; j++)
		{
			if (a[j] < a[i])
			{
				if (f[j] + 1 > f[i])
				{
					f[i] = f[j] + 1;
				}
			}
		}

	ll mx = 0;
	for (int i = 1; i <= n; i++)
	{
		if (f[i] > mx)
		{
			mx = f[i];
		}
	}
	return mx;
}

ll LCS()
{
	for (int i = 0; i < 5005; i++)
		for (int j = 0; j < 5005; j++)
			g[i][j] = 0;

	for(int i=1;i<=n;i++)
		for (int j = 1; j <= m; j++)
		{
			if (a[i] == b[j])
			{
				g[i][j] = g[i - 1][j - 1] + 1;
			}
			else
			{
				g[i][j] = max(g[i - 1][j], g[i][j - 1]);
			}
		}

	return g[n][m];
}



int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> b[i];
	}
	cout << LIS() << " " << LCS();

}

C-拿数问题 II

题目要求

YJQ 上完第10周的程序设计思维与实践后，想到一个绝妙的主意，他对拿数问题做了一点小修改，使得这道题变成了 拿数问题 II。
给一个序列，里边有 n 个数，每一步能拿走一个数，比如拿第 i 个数， Ai = x，得到相应的分数 x，但拿掉这个 Ai 后，x+1 和 x-1 (如果有 Aj = x+1 或 Aj = x-1 存在) 就会变得不可拿（但是有 Aj = x 的话可以继续拿这个 x）。求最大分数。
Input
第一行包含一个整数 n (1 ≤ n ≤ 105)，表示数字里的元素的个数
第二行包含n个整数a1, a2, …, an (1 ≤ ai ≤ 105)
Output
输出一个整数：n你能得到最大分值。
Example
Input
2
1 2
Output
2
Input
3
1 2 3
Output
4
Input
9
1 2 1 3 2 2 2 2 3
Output
10
Hint
对于第三个样例：先选任何一个值为2的元素，最后数组内剩下4个2。然后4次选择2，最终得到10分。

求解思路

1. 最优解性质：
   能得到的最大分值

2. 动态规划方程
   按照分值
   初始化： dp[0] = 0; dp[1] = arr[1];
   转移方程 : dp[i] = max(dp[i - 1], dp[i - 2] + arr[i]*i);
   其中arr[i]为大小为i的数的个数，dp[i]为小于i的数可取到的最大分值。

3. 自底向上（递推）或带备忘的自顶向下（记忆化搜索）方式计算最优值
   采用递推方式：
   通过一重循环更新dp数组的值

4. 构造最优解
   设给出的数字最大值为max
   最优解为 dp[max]，因为1 ≤ ai ≤ 10^5，所以可以直接取dp[100003]

5. 时间复杂度 O(n)

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
typedef long long ll;
using namespace std;


ll arr[100005];
ll dp[100005];
int main()
{
	ll n;
	cin >> n;
	for (ll i = 0; i < 10005; i++)
	{
		arr[i] = 0;
		dp[i] = 0;
	}
	for (ll i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		arr[tmp]++;
	}
	dp[0] = 0;
	dp[1] = arr[1];
	for (ll i = 2; i < 100005; i++)
	{
		dp[i] = max(dp[i - 1], dp[i - 2] + arr[i]*i);
	}
	cout << dp[100003];
}

转载：https://blog.csdn.net/qq_44099163/article/details/105765734