https://www.nowcoder.com/acm/contest/127/L
L 小小粉刷匠
题意:给一个大小为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=2476Time 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 7题意:给出两个串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离线版下载