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个整数，表示对于墙的每一段指定的颜色。
输出描述:
输出一个数,表示小名最少刷多少次。
输入例子:
3 3
1 2 1
输出例子:
2
-->
示例1
输入
3 3
1 2 1
输出
2
示例2
输入
5 4
5 4 3 3 4
输出
3
题意：给一个大小为n的数组SKT和一个大小为n的空数组，一次只能将空数组一个区间(区间大小为(1~k))的值设置为同一个数，问最少操作几次能将空数组改成该数组。
题解：见下面一题的题解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
int dp[][];
int qwq[];
memset(dp,0x3f3f3f3f,sizeof(dp));
int n, k;
scanf("%d%d",&n,&k);
for (int i = ; i < n; i++) {
scanf("%d", &qwq[i]);
}
for (int i = n - ; i >= ; i--) {
for (int j = i; j < n; j++) {
if (i == j)dp[i][j] = ;
else dp[i][j] = dp[i + ][j]+;
for (int skt = i + ; skt < i + k&&skt<=j; skt++) {
if (qwq[skt] == qwq[i]) {
if (skt == j) {
dp[i][j] = min(dp[i][j], dp[i + ][j]);
}
else dp[i][j] = min(dp[i][j], dp[i + ][skt] + dp[skt + ][j]);
}
}
}
}
cout << dp[][n - ] << endl;
// cout << sizeof(int) * 24300000/1024<<"KB" << endl;
return ;
}
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.
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）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
int dp[][];
int ans[];
char s1[], s2[];
while (scanf("%s%s", s1, s2) != EOF) {
int len = strlen(s1);
memset(ans, 0x3f3f3f3f, sizeof(ans));
memset(dp, , sizeof(dp));//dp[i][j]当S1为空串时区间i~j的最小需要改动次数
for (int i = len - ; i >= ; i--) {//倒着来是因为更新的时候使用的dp[i+1][k]，需要dp[i+1][k]已经是最优
for (int j = i; j < len; j++) {
if (i == j)
dp[i][j] = ;
else
dp[i][j] = dp[i + ][j] + ;//不考虑是否存在相等的字母时，直接在i的位置上涂改，在原来的次数上+1
for (int k = i + ; k <= j; k++) {
if (s2[i] == s2[k]) {//考虑存在字母已经被涂改成与i位置需要涂改的字母，这里i就可以随着那个k进行涂改
if (k == j) {
dp[i][j] = min(dp[i][j], dp[i + ][j]);
}
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]的最优性
dp[i][j] = min(dp[i][j], dp[i + ][k] + dp[k + ][j]);
}
}
}
}
}
for (int i = ; i < len; i++) {
ans[i] = dp[][i];
}
if (s1[] == s2[])ans[] = ;
for (int i = ; i < len; i++) {
if (s1[i] == s2[i]) {//二者字母相同时，则不需要涂改
ans[i] = ans[i - ];
}
else {
for (int j = ; j < i; j++) {//二者字母不相同时，和S1是空串的状况一样..所以可以使用dp数组更新
ans[i] = min(ans[i], ans[j] + dp[j + ][i]);
}
}
}
cout << ans[len - ] << endl;
}
return ;
}