devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

区间DP

作者：你好赵伟 | 2024-04-27 21:35:01

赞

踩

区间DP

目录

一，第一类区间DP

CSU 1172 Generating Queue（双端队列的选取问题）

CSU 1515 Sequence

CSU 1729 齿轮传动

CSU 内部题 treat（​2017年院赛C题）

力扣 375. 猜数字大小 II

力扣 553. 最优除法

力扣 647. 回文子串

力扣 2707. 字符串中的额外字符

力扣 3018. 可处理的最大删除操作数 I

二，第二类区间DP

CSU 1592 石子归并

UVA 10003 Cutting Sticks（切棍子）

HDU 5184 Brackets

力扣 664. 奇怪的打印机

力扣 面试题 08.14. 布尔运算

一，第一类区间DP

第一类区间DP的良基集合是{(x,y)|0<x<y<n}，也就是三角形。

双数列DP的良基集合是{(x,y)|0<x<n，0<y<n}，也就是矩形。

这个三角形就是这个矩形及其对角线组成的直角三角形。

第一类区间DP的递推式和双数列DP的递推式相同：

f(a,b) = g(f(a,b-c1), f(a+c2,b), f(a+c3,b-c4), a, b)，一般c1=c2=c3=c4=1

第一类区间DP和第一类数学归纳法其实差不多。

CSU 1172 Generating Queue（双端队列的选取问题）

题目：


Description

       对于一个由N个数字组成的队列s，我们每次操作都是把队列s中位于队首的数字拿出，然后将其放置到队列t的队首或队尾的位置。

       现有另外一个由N个数字组成的队列g，若队列t一开始为空，一直重复上述操作直到队列s为空为止，那么是否存在一种放置方案使得最后队列t与队列g从队首到队尾完全相同呢？


Input

       输入包含若干组数据。每组数据的第一行有1个正整数N(1<=N<=10^3)，N的含义同上，接下来一行有N个0-9的数字，依次表示队列g中的各个数字，再接下来一行也有N个0-9的数字，依次表示队列s中的各个数字。默认两个队列的左端为队首，右端为队尾。


Output

       对于每组数据，如果存在一种放置方案使得最后队列t与队列g从队首到队尾完全相同，输出“YES”，否则输出“NO”。


Sample Input

3
1 2 3
3 1 2

4
1 2 1 3
2 1 3 1


Sample Output

NO
YES


Hint

Sample 1：

      首先将3放入到队列t中，然后1可以放到队首形成1 3，也可以放到队尾形成3 1，但接下来对于前面两种情况，无论2放到队首还是放到队尾，都没办法形成1 2 3。

Sample 2：

      可行的放置策略为：首先将2放入到队列t中，然后将1放到队尾形成2 1，接下来将3放到队尾形成2 1 3，最后将1放到队首形成1 2 1 3。

思路：动态规划

dp[i][j]表示队列S的前j-i+1个数依次取出来能不能得到队列g的从i到j这一段

代码：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int dp[1001][1001], g[1001], s[1001];
  5.  
  6. int f(int low, int high)
  7. {
  8. 	if (low > high)return true;
  9. 	if (dp[low][high]>-1)return dp[low][high];
  10. 	bool flag = false;
  11. 	if (g[high] == s[high - low + 1])flag = flag || f(low, high - 1);
  12. 	if (g[low]  == s[high - low + 1])flag = flag || f(low + 1, high);
  13. 	dp[low][high] = flag;
  14. 	return flag;
  15. }
  16.  
  17. int main()
  18. {
  19. 	int n;
  20. 	while (cin >> n)
  21. 	{
  22. 		for (int i = 1; i <= n; i++)cin >> g[i];
  23. 		for (int i = 1; i <= n; i++)
  24. 		{
  25. 			cin >> s[i];
  26. 			for (int j = 1; j <= n; j++)dp[i][j] = -1;
  27. 		}
  28. 		if (f(1, n))cout << "YES\n";
  29. 		else cout << "NO\n";
  30. 		
  31. 	}
  32. 	return 0;
  33. }

CSU 1515 Sequence

题目：

Description

Give you a sequence consisted of n numbers. You are required to answer how many pairs of numbers (ai, aj) satisfy that | ai - aj | = 1 and L ≤ i < j ≤ R.

Input

The input consists of one or more test cases.
For each case, the first line contains two numbers n and m, which represent the length of the number sequence and the number of queries. ( 1 ≤ n ≤ 10^4, 1 ≤ m ≤ 10^5 )
The second line consists of n numbers separated by n - 1 spaces.( 0 ≤ ai < 2^31 )
Then the m lines followed each contain two values Li and Ri.

Output

For each case just output the answers in m lines.

Sample Input

  1. 10 10
  2. 5 5 1 3 6 3 5 7 1 7
  3. 3 4
  4. 6 8
  5. 8 9
  6. 2 8
  7. 5 7
  8. 6 7
  9. 1 9
  10. 3 10
  11. 3 10
  12. 5 6

Sample Output

  1. 0
  2. 0
  3. 0
  4. 3
  5. 1
  6. 0
  7. 4
  8. 3
  9. 3
  10. 0

这个题目我就是用动态规划来做的。

递推式是：

  1. r[i][j] = r[i + 1][j] - r[i + 1][j - 1] + r[i][j - 1];
  2. if (list[i] - list[j] == 1 || list[i] - list[j] == -1)r[i][j]++;

不过有1个问题，n有1万，1万乘以1万的数组不仅仅是超题目给的内存，而是直接就runtime error了。

错误代码：

  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4.  
  5. int list[10001];
  6. int r[10001][10001];
  7.  
  8. int main()
  9. {
  10. 	int n, m;
  11. 	int start, endd;
  12. 	memset(r, 0, sizeof(r));
  13. 	while (cin >> n >> m)
  14. 	{
  15. 		for (int i = 1; i <= n; i++)cin >> list[i];
  16. 		for (int j = 2; j <= n; j++)
  17. 		{
  18. 			for (int i = j - 1; i >= 1; i--)
  19. 			{
  20. 			r[i][j] = r[i + 1][j] - r[i + 1][j - 1] + r[i][j - 1];
  21. 			if (list[i] - list[j] == 1 || list[i] - list[j] == -1)r[i][j]++;
  22. 			}
  23. 		}
  24. 		while (m--)
  25. 		{
  26. 			cin >> start >> endd;
  27. 			cout << r[start][endd] << endl;
  28. 		}
  29. 	}
  30. 	return 0;
  31. }

于是我只好把r变成1000*1000的数组。

这样，r就只能存储那些2个下标都是10的倍数的区间。

在计算这个r时，递推式略有变化。

假如a<b<c<d，用f来表示最后要求的那个答案，即要输出的数，那么，

f(a,d)=f(a,c)+f(b,d)-f(b,c)+x，其中x是从a到b的区间中选1个数，从c到d的区间选1个数，一共有多少对数满足条件。

在本题里面，用g函数计算x，不过递推式没有上述的递推式那么广泛，

因为仍然是用动态规划做的，所以b-a都是10或者0，d-c都是10或者0。

注意，实际上abcd并不是严格递增的，所以g函数里面sum++的条件必须有i<j

正确的代码：

  1. #include<iostream>
  2. #include<string.h>
  3. #include<math.h>
  4. using namespace std;
  5.  
  6. int list[10001];
  7. int r[1001][1001];
  8.  
  9. int g(int s,int e)
  10. {
  11. 	int sum = 0;
  12. 	for (int i = s; i < s + 10;i++)	for (int j = e; j>e - 10;j--)
  13. 	if (i < j && list[i] == list[j] + 1 || list[i] == list[j] - 1)sum++;
  14. 	return sum;
  15. }
  16.  
  17. int main()
  18. {
  19. 	int n, m;
  20. 	int s, e;
  21. 	int s10, e10;
  22. 	int sum;
  23. 	memset(r, 0, sizeof(r));
  24. 	while (cin >> n >> m)
  25. 	{
  26. 		for (int i = 0; i < n; i++)cin >> list[i];
  27. 		for (int j = 1; j <= (n - 1) / 10; j++)for (int i = j - 1; i >= 0; i--)
  28. 		r[i][j] = r[i + 1][j] - r[i + 1][j - 1] + r[i][j - 1] + g(i * 10, j * 10);
  29. 		while (m--)
  30. 		{
  31. 			cin >> s >> e;
  32. 			s--;
  33. 			e--;
  34. 			s10 = (s + 9) / 10;
  35. 			e10 = e / 10;
  36. 			sum = r[s10][e10];
  37. 		for (int i = s; i < s10 * 10; i++)for (int j = i + 1; j <= e; j++)
  38. 			if (list[i] == list[j] + 1 || list[i] == list[j] - 1)sum++;
  39. 		for (int j = e10 * 10 + 1; j <= e; j++)for (int i = s10 * 10; i < j;i++)
  40. 			if (list[i] == list[j] + 1 || list[i] == list[j] - 1)sum++;
  41. 			cout << sum << endl;
  42. 		}
  43. 	}
  44. 	return 0;
  45. }

CSU 1729 齿轮传动

题目：

Description

你在一家机械厂打工，你的老板让你把一组齿轮种类序列a1,a2,..,an取走几个让齿轮的传动比为1:1，老板要求你取走最少的齿轮，不能改变齿轮原来的相对位置，满足条件，即齿轮种类组合起

来是回文串。

Input

多组数据，第一行有一个整数T ， 表示有T组数据。(T<=100)

以下每组数据第一行有一个整数n ， 表示n个齿轮(1<=n<=1000)

接下来一行有n个整数a1,a2,…,an表示齿轮种类 (1<=ai<=10000)

Output

取走的最少齿轮数

Sample Input

1
4
1 2 3 1

Sample Output

1

这个题目，传动比为1:1是什么意思，其实我不太理解。

不过无所谓，反正就是去掉一些数字，剩下的构成回文串。

我是用动态规划做的，时间比较长，696ms

代码：

  1. #include<iostream>;
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int t;
  7.     cin >> t;
  8.     int n;
  9.     while (t--)
  10.     {
  11.         cin >> n;
  12.         int *a = new int[n];
  13.         for (int i = 0; i < n; i++)cin >> a[i];
  14.          
  15.         int **list = new int *[n];
  16.         for (int i = 0; i < n; i++)list[i] = new int[n];
  17.         for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)list[i][j] = 0;
  18.         for (int i = 0; i < n; i++)list[i][i] = 1;
  19.  
  20.         for (int i = n-1; i >=0 ; i--)
  21.         {
  22.             for (int j = i + 1; j < n; j++)
  23.             {
  24.                 list[i][j] = list[i + 1][j];
  25.                 if (list[i][j - 1]>list[i][j])list[i][j] = list[i][j - 1];
  26.                 if (list[i + 1][j - 1] + 2>list[i][j] && a[i] == a[j])list[i][j] = list[i + 1][j - 1] + 2;
  27.             }
  28.         }
  29.         cout << n - list[0][n - 1]<<endl;
  30.     }
  31.     return 0;
  32. }

CSU 内部题 treat（​2017年院赛C题）

题目：

描述

给出长度为N的数列{A_i}，每次可以从最左边或者最右边取走一个数，第i次取数得到的价值是i*A_j。求价值之和最大的取数方案。

输入格式

第一行，一个整数，表示数列长度N。
接下来N行，每行一个整数，表示数列A_i。

N<=2000,A_i<=1000

输出格式

一个整数，表示最大的价值之和。

测试样例1

输入

5
1
3
1
5
2

输出

43

代码：

  1. #include<iostream>
  2. using namespace std;
  3. int n,list[2000],ans[2000][2000];
  4.  
  5. int f(int low,int high)
  6. {
  7. 	if(ans[low][high]>=0)return ans[low][high];
  8. 	if(low==high)return list[low]*n;
  9. 	int a=f(low,high-1)+list[high]*(n-high+low);
  10. 	ans[low][high]=f(low+1,high)+list[low]*(n-high+low);
  11. 	if(ans[low][high]<a)ans[low][high]=a;
  12. 	return ans[low][high];
  13. }
  14.  
  15. int main()
  16. {
  17. 	cin>>n;
  18. 	for(int i=0;i<n;i++)cin>>list[i];
  19. 	for(int i=0;i<n;i++)for(int j=i;j<n;j++)ans[i][j]=-1;
  20. 	cout<<f(0,n-1);
  21. 	return 0;
  22. }

力扣 375. 猜数字大小 II

博弈

力扣 553. 最优除法

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。

  • 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意：你的表达式不应该包含多余的括号。

示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

示例 2:

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

说明:

  • 1 <= nums.length <= 10
  • 2 <= nums[i] <= 1000
  • 对于给定的输入只有一种最优除法。
  1.  
  2. class Solution {
  3. public:
  4. 	string optimalDivision(vector<int>& nums) {
  5. 		this->nums = nums;
  6. 		mmax.clear();
  7. 		mmin.clear();
  8. 		dp(0, nums.size() - 1);
  9. 		return makeString(nums,0, nums.size() - 1, true);
  10. 	}
  11. 	string makeString(vector<int>& nums, int low, int high, bool needMax) {
  12. 		if (low == high)return to_string(nums[low]);
  13. 		int id = needMax ? maxid[low][high] : minid[low][high];
  14. 		string s1 = makeString(nums, low, id, needMax), s2 = makeString(nums, id + 1, high, !needMax);
  15. 		if (high - id > 1)s2 = "(" + s2 + ")";
  16. 		return s1 + "/" + s2;
  17. 	}
  18. 	void dp(int low, int high) {
  19. 		if (low == high) {
  20. 			mmax[low][high] = mmin[low][high] = nums[low];
  21. 			//maxid[low][high] = minid[low][high] = low;
  22. 			return;
  23. 		}
  24. 		if (mmax[low].find(high) != mmax[low].end())return;
  25. 		float maxs, mins;
  26. 		for (int i = low; i < high; i++) {
  27. 			dp(low, i);
  28. 			dp(i + 1, high);
  29. 			float x = mmax[low][i] / mmin[i + 1][high];
  30. 			float y = mmin[low][i] / mmax[i + 1][high];
  31. 			if (i == low) {
  32. 				maxs = x, mins = y, maxid[low][high] = low, minid[low][high] = low;
  33. 				continue;
  34. 			}
  35. 			if (maxs < x) {
  36. 				maxs = x, maxid[low][high] = i;
  37. 			}
  38. 			if (mins > y) {
  39. 				mins = y, minid[low][high] = i;
  40. 			}
  41. 		}
  42. 		mmax[low][high] = maxs;
  43. 		mmin[low][high] = mins;
  44. 	}
  45. 	vector<int> nums;
  46. 	map<int, map<int, float>>mmax;
  47. 	map<int, map<int, float>>mmin;
  48. 	map<int, map<int, int>>maxid;
  49. 	map<int, map<int, int>>minid;
  50. };

力扣 647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成
  1. class Solution {
  2. public:
  3. 	int countSubstrings(string s) {
  4. 		this->s = s;
  5. 		int ans = 0;
  6. 		for (int i = 0; i < s.length(); i++)for (int j = i; j < s.length(); j++)ans += (dp(i, j) > 0);
  7. 		return ans;
  8. 	}
  9. 	int dp(int low, int high) {
  10. 		if (low >= high)return 1;
  11. 		if (m[low][high])return m[low][high];
  12. 		if (s[low] != s[high])return -1;
  13. 		return m[low][high] = dp(low + 1, high - 1);
  14. 	}
  15. 	string s;
  16. 	map<int, map<int, int>>m;
  17. };

力扣 2707. 字符串中的额外字符

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ，使剩下的字符 最少 。

示例 1：

输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
输出：1
解释：将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。

示例 2：

输入：s = "sayhelloworld", dictionary = ["hello","world"]
输出：3
解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。

提示：

  • 1 <= s.length <= 50
  • 1 <= dictionary.length <= 50
  • 1 <= dictionary[i].length <= 50
  • dictionary[i] 和 s 只包含小写英文字母。
  • dictionary 中的单词互不相同。
  1. class Solution {
  2. public:
  3.     int minExtraChar(string s, vector<string>& dictionary) {
  4.         map<string,int>m;
  5.         for(auto s:dictionary)m[s]=1;
  6.         map<int,map<int,int>>has;
  7.         for(int i=0;i<s.length();i++){
  8.             string x = "";
  9.             for(int j=i;j<s.length();j++){
  10.                 x+=s[j];
  11.                 has[i][j]=m[x];
  12.             }
  13.         }
  14.         this->m.clear();
  15.         return s.length()-dp(has,0,s.length()-1);
  16.     }
  17.     int dp(map<int,map<int,int>>&has,int low,int high){
  18.         if(low>high)return 0;        
  19.         if(m[low][high])return m[low][high]-1;
  20.         int ans=dp(has,low+1,high);
  21.         for(int i=low;i<=high;i++){
  22.             if(has[low][i])ans=max(ans,i+1-low+dp(has,i+1,high));
  23.         }
  24.         m[low][high]=ans+1;
  25.         return ans;
  26.     }
  27.     map<int,map<int,int>>m;//能覆盖的最大数量
  28. };

力扣 3018. 可处理的最大删除操作数 I

给定一个下标 从 0 开始 的数组 nums 和一个下标 从 0 开始 的数组 queries。

你可以在开始时执行以下操作 最多一次：

  • 用 nums 的 

    子序列

     替换 nums。

我们以给定的queries顺序处理查询；对于queries[i]，我们执行以下操作：

  • 如果 nums 的第一个 和 最后一个元素 小于 queries[i]，则查询处理 结束。
  • 否则，从 nums 选择第一个 或 最后一个元素，要求其大于或等于 queries[i]，然后将其从 nums 中 删除。

返回通过以最佳方式执行该操作可以处理的 最多 次数。

示例 1：

输入：nums = [1,2,3,4,5], queries = [1,2,3,4,6]
输出：4
解释：我们不执行任何操作，并按如下方式处理查询：
1- 我们选择并移除 nums[0]，因为 1 <= 1，那么 nums 就变成 [2,3,4,5]。
2- 我们选择并移除 nums[0]，因为 2 <= 2，那么 nums 就变成 [3,4,5]。
3- 我们选择并移除 nums[0]，因为 3 <= 3，那么 nums 就变成 [4,5]。
4- 我们选择并移除 nums[0]，因为 4 <= 4，那么 nums 就变成 [5]。
5- 我们不能从 nums 中选择任何元素，因为它们不大于或等于 5。
因此，答案为 4。
可以看出，我们不能处理超过 4 个查询。

示例 2：

输入：nums = [2,3,2], queries = [2,2,3]
输出：3
解释：我们不做任何操作，按如下方式处理查询：
1- 我们选择并移除 nums[0]，因为 2 <= 2，那么 nums 就变成 [3,2]。
2- 我们选择并移除 nums[1]，因为 2 <= 2，那么 nums 就变成 [3]。
3- 我们选择并移除 nums[0]，因为 3 <= 3，那么 nums 就变成 []。
因此，答案为 3。
可以看出，我们不能处理超过 3 个查询。

示例 3：

输入：nums = [3,4,3], queries = [4,3,2]
输出：2
解释：首先，我们用 nums 的子序列 [4,3] 替换 nums。
然后，我们可以按如下方式处理查询：
1- 我们选择并移除 nums[0]，因为 4 <= 4，那么 nums 就变成 [3]。
2- 我们选择并移除 nums[0]，因为 3 <= 3，那么 nums 就变成 []。
3- 我们无法处理更多查询，因为 nums 为空。
因此，答案为 2。
可以看出，我们不能处理超过 2 个查询。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= queries.length <= 1000
  • 1 <= nums[i], queries[i] <= 109

思路：

关键就是理解题意。"如果 nums 的第一个 和 最后一个元素 小于 queries[i]，则查询处理 结束。"这句话的意思原来是本次查询结束，继续下次查询，而不是所有查询全部结束。

  1. class Solution {
  2. public:
  3. 	int maximumProcessableQueries(vector<int>& nums, vector<int>& queries) {
  4. 		vector<int>v(nums.size(), 0);
  5. 		for (int d = nums.size() - 2; d >= 0; d--) {
  6. 			for (int i = nums.size() - d - 1; i >= 0; i--) {
  7. 				if (i + d + 1 < nums.size()) {
  8. 					v[i] += (nums[i + d + 1] >= queries[v[i]]);
  9. 				}
  10. 				if (i) {
  11. 					int n = v[i - 1];
  12. 					v[i] = max(v[i], n + (nums[i - 1] >= queries[n]));
  13. 				}
  14. 				if(v[i] >= queries.size())return v[i];
  15. 			}
  16. 		}
  17. 		int ans = 0;
  18. 		for (int i = 0; i < nums.size(); i++) {
  19. 			ans = max(ans, v[i] + (nums[i] >= queries[v[i]]));
  20. 		}
  21. 		return ans;
  22. 	}
  23. };

二，第二类区间DP

第二类区间DP和第一类区间DP的良基集合相同。

第二类区间DP的递推式：f(a,b) = g(S, a, b)，其中集合S={h(f(a,t), f(t+1,b)) | a<=t<=b}

CSU 1592 石子归并

题目：

Description

现在有n堆石子，第i堆有ai个石子。现在要把这些石子合并成一堆，每次只能合并相邻两个，每次合并的代价是两堆石子的总石子数。求合并所有石子的最小代价。

Input

第一行包含一个整数T（T<=50），表示数据组数。
每组数据第一行包含一个整数n（2<=n<=100），表示石子的堆数。
第二行包含n个正整数ai（ai<=100），表示每堆石子的石子数。

Output

每组数据仅一行，表示最小合并代价。

Sample Input

  1. 2
  2. 4
  3. 1 2 3 4
  4. 5
  5. 3 5 2 1 4

Sample Output

  1. 19
  2. 33

如果不是排成一列，任意2堆都可以合并的话，那就是贪心问题，参考CSU 1588: 合并果子 https://blog.csdn.net/nameofcsdn/article/details/112754030

本题，是动态规划问题。

代码：

  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4.  
  5. int list[101];
  6. int sum[101][101];
  7.  
  8. int f(int start, int end)
  9. {
  10. 	if (sum[start][end] >= 0)return sum[start][end];
  11. 	if (start == end)return 0;
  12. 	if (start + 1 == end)return list[start] + list[end];
  13. 	int min = 1000000, temp;
  14. 	for (int i = start; i < end; i++)
  15. 	{
  16. 		temp = f(start, i) + f(i + 1, end);
  17. 		if (min>temp)min = temp;
  18. 	}
  19. 	for (int i = start; i <= end; i++)min += list[i];
  20. 	sum[start][end] = min;
  21. 	return min;
  22. }
  23.  
  24. int main()
  25. {
  26. 	int cas;
  27. 	cin >> cas;
  28. 	int n;
  29. 	while (cas--)
  30. 	{
  31. 		cin >> n;
  32. 		for (int i = 1; i <= n; i++)cin >> list[i];
  33. 		memset(sum, -1, sizeof(sum));
  34. 		cout << f(1, n) << endl;
  35. 	}
  36. 	return 0;
  37. }

如果N再大一些，就只能用专门的最优二叉树算法来做，参考石子合并 HYSBZ - 3229 最优二叉搜索树

UVA 10003 Cutting Sticks（切棍子）

题目：

You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work requires that they only make one cut at a time. 

It is easy to notice that different selections in the order of cutting can led to different prices. 

For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price. 

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.
Input
The input will consist of several input cases. The first line of each test case will contain a positive number l that represents the length of the stick to be cut. You can assume l < 1000. 

The next line will contain the number n (n < 50) of cuts to be made. The next line consists of n positive numbers ci (0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order. 

An input case with l = 0 will represent the end of the input.
Output
You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of cutting the given stick. Format the output as shown below.
Sample Input

100

3 

25 50 75 

10 

4 

4 5 7 8 

0
Sample Output
The minimum cutting is 200. 

The minimum cutting is 22.

这个题目，首先要理解它是什么意思。

假设每次切棍子的代价都为棍子的长度，求总代价的最小值。

以100,3,25,50,75为例，先从50的地方切开，产生2个长为50的块，代价为100，

然后2次切都是切长为50的棍子，代价都是50，所以总代价为200。

这么看起来，这个问题和 CSU - 1592 石子归并 是一模一样的

代码：

  1. #include<iostream>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int list[52];
  7. int r[52][52];
  8. int a;
  9.  
  10. int f(int start, int end)
  11. {
  12. 	if (r[start][end] >= 0)return r[start][end];
  13. 	if (start + 1 == end)return list[end] - list[start];
  14. 	r[start][end] = 100000;
  15. 	for (int k = start + 1; k < end; k++)
  16. 	{
  17. 		a = f(start, k) + f(k, end);
  18. 		if (r[start][end]>a)r[start][end] = a;
  19. 	}
  20. 	r[start][end] += list[end] - list[start];
  21. 	return r[start][end];
  22. }
  23.  
  24. int main()
  25. {
  26. 	int l, n;
  27. 	while (cin >> l)
  28. 	{
  29. 		if (l == 0)break;
  30. 		cin >> n;
  31. 		for (int i = 1; i <= n; i++)cin >> list[i];
  32. 		list[0] = 0;
  33. 		list[n + 1] = l;
  34. 		memset(r, -1, sizeof(r));
  35. 		cout << "The minimum cutting is " << f(0, n + 1) - l << "." << endl;
  36. 		
  37. 	}
  38. 	return 0;
  39. }
  40.

HDU 5184 Brackets

题目：

Description

We give the following inductive definition of a “regular brackets” sequence:

  • the empty sequence is a regular brackets sequence,
  • if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
  • if a and b are regular brackets sequences, then ab is a regular brackets sequence.
  • no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

  1. ((()))
  2. ()()()
  3. ([]])
  4. )[)(
  5. ([][][)
  6. end

Sample Output

  1. 6
  2. 6
  3. 4
  4. 0
  5. 6

这个题目有一个地方要注意，比如输入的是[][]，那么答案应该是4而不是2，

也就是说最外面的2个括号有时可以匹配，有时不能匹配，要看怎么样答案大一些。

然后直接就是记忆化搜索，思路上面没什么难的。

代码：

  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4.  
  5. char c[101];
  6. int list[101][101];
  7. int a;
  8.  
  9. int f(int i, int j)
  10. {
  11. 	if (list[i][j] >= 0)return list[i][j];
  12. 	if (i >= j)return 0;
  13. 	if (i + 1 == j)
  14. 	{
  15. 		if (c[i] == '('&& c[j] == ')' || c[i] == '['&& c[j] == ']')list[i][j] = 1;
  16. 		else list[i][j] = 0;
  17. 		return list[i][j];
  18. 	}
  19. 	if (c[i] == '('&& c[j] == ')' || c[i] == '['&& c[j] == ']')list[i][j] = f(i + 1, j - 1) + 1;
  20. 	for (int k = i; k < j; k++)
  21. 	{
  22. 		a = f(i, k) + f(k + 1, j);
  23. 		if (list[i][j] < a)list[i][j] = a;
  24. 	}	
  25. 	return list[i][j];
  26. }
  27.  
  28. int main()
  29. {
  30. 	while (cin.getline(c, 101))
  31. 	{
  32. 		if (c[0] == 'e')break;
  33. 		int l = strlen(c);
  34. 		memset(list, -1, sizeof(list));
  35. 		cout << f(0, l - 1) * 2 << endl;
  36. 	}
  37. 	return 0;
  38. }

力扣 664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

 
示例 1：

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。
示例 2：

输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
 

提示：

1 <= s.length <= 100
s 由小写英文字母组成

思路：

枚举分析哪个字符和首字符相同，考虑他们是同一次打出来的场景。

本质上就是对字符串进行分割，和石子归并很像。

  1. class Solution {
  2. public:
  3. 	map<int,map<int, int>>m;
  4. 	int dp(string &s, int low, int high)
  5. 	{
  6. 		if (low > high)return 0;
  7. 		if (low == high)return 1;
  8. 		if (m[low][high])return m[low][high];		
  9. 		if (s[low] == s[low + 1])return  m[low][high] = dp(s, low + 1, high);
  10. 		if (s[high] == s[high - 1])return  m[low][high] = dp(s, low, high-1);
  11. 		int ans = dp(s, low + 1, high) + 1;
  12. 		for (int i = low + 1; i < high; i++) {
  13. 			if (s[i] == s[low])ans = min(ans, dp(s, low, i) + dp(s, i, high) - 1);
  14. 		}
  15. 		if (s[low] == s[high])ans = min(ans, dp(s, low + 1, high - 1) + 1);
  16. 		return m[low][high] = ans;
  17. 	}
  18. 	int strangePrinter(string s) {
  19. 		m.clear();
  20. 		return dp(s, 0, s.length() - 1);
  21. 	}
  22. };

力扣 面试题 08.14. 布尔运算

给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。

示例 1:

输入: s = "1^0|0|1", result = 0

输出: 2
解释: 两种可能的括号方法是
1^(0|(0|1))
1^((0|0)|1)

示例 2:

输入: s = "0&0&0&1^1|0", result = 1

输出: 10

提示：

  • 运算符的数量不超过 19 个
  1. class Solution {
  2. public:
  3. 	int countEval(string s, int result) {
  4. 		return countEval(s)[result];
  5. 	}
  6. 	vector<int> countEval(string s) {
  7. 		if (s.length() == 1) {
  8. 			int x = s[0] - '0';
  9. 			return vector<int>{1 - x, x};
  10. 		}
  11. 		if (m.find(s) != m.end())return m[s];
  12. 		vector<int>v(2);
  13. 		for (int i = 1; i < s.length(); i += 2) {
  14. 			vector<int>v1 = countEval(s.substr(0, i));
  15. 			vector<int>v2 = countEval(s.substr(i + 1, s.length() - i - 1));
  16. 			int a = v1[0] * v2[0] + v1[1] * v2[1];
  17. 			int b = v1[0] * v2[1] + v1[1] * v2[0];
  18. 			if (s[i] == '|')v[0] += v1[0] * v2[0], v[1] += b + v1[1] * v2[1];
  19. 			if (s[i] == '&')v[0] += v1[0] * v2[0] + b, v[1] += v1[1] * v2[1];
  20. 			if (s[i] == '^')v[0] += a, v[1] += b;
  21. 		}
  22. 		return m[s]=v;
  23. 	}
  24. 	map<string, vector<int>>m;
  25. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/498805
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号