【湖南师范大学2018年大学生程序设计竞赛新生赛 L】【HDOJ2476】【区间DP】

it2022-05-05  132

https://www.nowcoder.com/acm/contest/127/L

L 小小粉刷匠

题目描述

"lalala,我是一个快乐的粉刷匠",小名一边快活地唱着歌,一边开心地刷着墙",兴致突然被打断,"小名,你今天如果刷不完这一栋楼的墙,那么你就等着被炒鱿鱼吧",老板声嘶力竭的吼着。苦恼的小名因为不想被炒鱿鱼,所以希望尽量快地刷完墙,由于他本人的数学基础很差,他现在请你来帮助他计算最少完成每一堵墙需要刷多少次。每一面墙有n个段,对于每个段指定一个目标颜色ci。刚开始的时候所有的墙壁为白色,我们现在有一个刷子,刷子长度为k,刷子每次可以选择一种颜色,然后选择段数为(1~k)连续的墙段刷成选择的一种颜色。我们现在想要知道,为了把墙变成目标颜色,最少刷多少次(保证指定的目标颜色一定不为白色)。

输入描述:

对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,1<=k<=50,k<n),表示墙的长度为n,刷子的长度为k。第二行输入n个整数,表示对于墙的每一段指定的颜色。

输出描述:

输出一个数,表示小名最少刷多少次。 示例1

输入

3 3 1 2 1

输出

2 示例2

输入

5 4 5 4 3 3 4

输出

3

题意:给一个大小为n的数组SKT和一个大小为n的空数组,一次只能将空数组一个区间(区间大小为(1~k))的值设置为同一个数,问最少操作几次能将空数组改成该数组。

题解:见下面一题的题解。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int main() { 7 int dp[102][102]; 8 int qwq[102]; 9 memset(dp,0x3f3f3f3f,sizeof(dp)); 10 int n, k; 11 scanf("%d%d",&n,&k); 12 for (int i = 0; i < n; i++) { 13 scanf("%d", &qwq[i]); 14 } 15 for (int i = n - 1; i >= 0; i--) { 16 for (int j = i; j < n; j++) { 17 if (i == j)dp[i][j] = 1; 18 else dp[i][j] = dp[i + 1][j]+1; 19 for (int skt = i + 1; skt < i + k&&skt<=j; skt++) { 20 if (qwq[skt] == qwq[i]) { 21 if (skt == j) { 22 dp[i][j] = min(dp[i][j], dp[i + 1][j]); 23 } 24 else dp[i][j] = min(dp[i][j], dp[i + 1][skt] + dp[skt + 1][j]); 25 } 26 } 27 } 28 } 29 cout << dp[0][n - 1] << endl; 30 // cout << sizeof(int) * 24300000/1024<<"KB" << endl; 31 return 0; 32 } View Code http://acm.hdu.edu.cn/showproblem.php?pid=2476

String painter

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6211    Accepted Submission(s): 2992

Problem Description There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?   Input Input contains multiple cases. Each case consists of two lines: The first line contains string A. The second line contains string B. The length of both strings will not be greater than 100.   Output A single line contains one integer representing the answer.   Sample Input zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd   Sample Output 6

题意:给出两个串s1和s2,一次只能将一个区间刷一次,问最少几次能让s1=s2

题解:看到区间,又是找最少操作次数,想到区间DP。

首先简化一下问题:假如S1本身是一个空串,则问题等同于上一题,则可以使用dp(i,j)表示涂改 i~j 这个区间所需要的最少次数,在涂改位置i的时候,可以看出来如果S1串已经涂改过的字母中不含有与位置 i 要改变成的字母相同的字母,则有dp(i,j)=dp(i+1,j)+1,如果存在相同字母,则可以在那个位置涂改的时候顺便把位置i涂改,此时也就可以进行更新dp(i,j) = min(dp(i,j), dp(i + 1,k) + dp(k + 1,j));答案就是dp(0,n-1),这里也就是上一题的解法了。

而这题的S1不是空串,这和是空串有什么不一样的呢,S1不是空串,那么就有可能S1(i)==S2(i)那么这个时候不需要涂改,也就是ans(i)=ans(i-1),这也是唯一的区别,否则就使用由空串得到的dp数组进行更新,ans(i)=min(ans(i),ans(j)+dp(j+1,i))(其中0<=j&&j<=i)

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int main() { 7 int dp[102][102]; 8 int ans[102]; 9 char s1[102], s2[102]; 10 while (scanf("%s%s", s1, s2) != EOF) { 11 int len = strlen(s1); 12 memset(ans, 0x3f3f3f3f, sizeof(ans)); 13 memset(dp, 0, sizeof(dp));//dp[i][j]当S1为空串时区间i~j的最小需要改动次数 14 for (int i = len - 1; i >= 0; i--) {//倒着来是因为更新的时候使用的dp[i+1][k],需要dp[i+1][k]已经是最优 15 for (int j = i; j < len; j++) { 16 if (i == j) 17 dp[i][j] = 1; 18 else 19 dp[i][j] = dp[i + 1][j] + 1;//不考虑是否存在相等的字母时,直接在i的位置上涂改,在原来的次数上+1 20 for (int k = i + 1; k <= j; k++) { 21 if (s2[i] == s2[k]) {//考虑存在字母已经被涂改成与i位置需要涂改的字母,这里i就可以随着那个k进行涂改 22 if (k == j) { 23 dp[i][j] = min(dp[i][j], dp[i + 1][j]); 24 } 25 else {//之所以使用dp[i+1][k]+dp[k+1][j]而不是直接dp[i+1][j]是因为dp[i+1][k]的涂改可以保证多涂改一个i不影响dp[i+1][k]的最优性,而不能保证dp[i+1][j]的最优性 26 dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]); 27 } 28 } 29 } 30 } 31 } 32 for (int i = 0; i < len; i++) { 33 ans[i] = dp[0][i]; 34 } 35 if (s1[0] == s2[0])ans[0] = 0; 36 for (int i = 1; i < len; i++) { 37 if (s1[i] == s2[i]) {//二者字母相同时,则不需要涂改 38 ans[i] = ans[i - 1]; 39 } 40 else { 41 for (int j = 0; j < i; j++) {//二者字母不相同时,和S1是空串的状况一样..所以可以使用dp数组更新 42 ans[i] = min(ans[i], ans[j] + dp[j + 1][i]); 43 } 44 } 45 } 46 cout << ans[len - 1] << endl; 47 } 48 return 0; 49 } View Code

 

转载于:https://www.cnblogs.com/MekakuCityActor/p/9715908.html

相关资源:HDOJ杭州电子科技大学ACM离线版下载

最新回复(0)