区间DP
首先引出问题：石子合并：
好像讲区间DP的都是先用石子合并，毕竟是老经典题目了。
一维区间DP：
石子合并
题目描述：有n堆石子排成一排，每堆石子有一定的数量。将n堆石子并成为一堆，每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求总的最小花费。
输入：第一行是整数n，表示有n堆石子。第二行有n个数，分别表示这n堆石子的数目。
输出：总的最小花费。
输入样例：
3
2 4 5
输出样例：
17
提示：样例的计算过程是：第一次合并2+4=6；第二次合并6+5=11；总花费6+11=17。
区间DP相当于盖楼层一样，当前层需要有下层构成，按算法上的说法就是这个需要在上一次的结果来构成，最初的状态是每个石头是一堆，然后代价就是它本身，然后每次合成都要花费两个的和，假设现在的状态是l到r的石子，他肯定可以分成两堆，然后把分成的两堆和起来就会加上他们的代价也就是
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
dp[i][j]表示从到
合成一堆需要的最小代价
dp[i][k]+dp[k+1][j]表示从k点断开就是用i到k这堆合并k+1到j合成一堆，那么需要每堆加上把这两堆合成的代价，也就是i到j全部石子的重量。
这里我们就知道如果我们要求得i到j（这时的长度是j-i）那么需要i-k和k+1 到 j（比j-i长度小的）所以就是从底层构成上层。
所以一般区间DP都是这样写：
for(int i=1;i<=n;i++) dp[i][i]=1;///初始状态
for(int len=2;len<=n;len++){///枚举长度
for(int i=1;i<=n-len+1;i++){///枚举左端点
int j=i+len-1;///对应的右端点 =左端点+长度-1;
dp[i][j]=inf;///初始化
for(int k=i;k<j;k++){///取最优
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
}
}
cout<<dp[1][n]<<endl;[CQOI2007]涂色PAINT
链接：https://ac.nowcoder.com/acm/problem/19909
来源：牛客网
题目描述
假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。
例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。
输入描述:
输入仅一行，包含一个长度为n的字符串，即涂色目标。
字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
输出描述:
仅一行，包含一个数，即最少的涂色次数。
示例1
输入
复制
AAAAA
输出
复制
1
示例2
输入
复制
RGBGR
输出
复制
3
题意：就是用空串刷成对应的字符串需要最小次数
思路：
定义dp[i][j]，表示在区间[i ,j]内从空白串转换到目标串时的最少步数。重点是区间两端的字符
st[i] 和str[j]，分析以下两种情况。
1. 若str[i] = str[j]。第一次刷用str[i]把区间[i , j]刷一遍，这个刷法肯定是最优的。如果分别去掉两个端点，得到2个区间[i + 1 , j]、[i , j − 1]，这2个区间的最小步数相等，也等于原区间[i , j]的最小步数。例如str[i , j]=“abbba”，先用"a"全部刷一遍，再刷1次"bbb"，共刷2次。如果去掉第一个"a"，剩下的"bbba"，也是刷2次。
2. 若str[i] ≠ str[j]。因为两端点不等，至少要各刷1次。用标准的区间操作，把区间分成[i,k]和[k+1,j]两部分，枚举最小步数。
其实就是在“石子合并”的基础上加上判断，判断是否首尾是否相等，相等肯定就可以少刷一端点，不相等就是“石子合并的那段代码”。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=1e9+7;
const int maxn=2e5+7;
ll n,m;
ll dp[1010][1010];
string str;
int main() {
cin>>str;
ll n=str.size();
str='#'+str;
for(int i=1;i<=n;i++) dp[i][i]=1;
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
dp[i][j]=mod;
if(str[i]==str[j]){
dp[i][j]=min(dp[i][j-1],dp[i+1][j]);
}else {
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
printf("%lld\n",dp[1][n]);
return 0;
}刷字符串扩展String painter
题目描述：给定两个长度相等的字符串A、B，由小写字母组成。一次操作，允许把A中的一个连续子串（区间）都转换为某个字符（就像用刷子刷成一样的字符）。要把A转换为B，问最低操作数是多少?
输入：第一行是字符串A，第二行是字符串B。两个字符串的长度不大于100。
输出：一个表示答案的整数。
输入样例：
zzzzzfzzzzz
abcdefedcba
输出样例：
6
提示：第1次把zzzzzfzzzzz转换为aaaaaaaaaaa，第2次转为abbbbbbbbba，第3次转为abccccccccba…
思路：
这个题就是上个题的扩展，在上个题刷空串的基础上，判断原串位置是否与目标串的位置是否相等，相等的话肯定不用在去刷那个位置了，就是从头枚举到最后取到最优，不等的话就在前面的状态转移到现在这个状态，使其最优。
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#pragma GCC optimize(2)
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=1e9+7;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
char str[maxn],s[maxn];
ll dp[1010][1010];
int main() {
while(~scanf("%s%s",str+1,s+1)) {
ll n=strlen(str+1);
for(int i=1; i<=n; i++) { ///初始化每个字符都至少要用一次刷
dp[i][i]=1;
}
///从空字符串开始刷
for(int len=2; len<=n; len++) {///区间长度
for(int i=1; i<=n-len+1; i++) {///左端点
int j=i+len-1;///右端点
dp[i][j]=mod;///初始化最大值
if(s[i]==s[j]) {
dp[i][j]=dp[i+1][j];
}else {
for(int k=i;k<j;k++){///区间转移
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
for(int i=1;i<=n;i++){
if(str[i]==s[i])///相同位置相同
dp[1][i]=dp[1][i-1];
else {
for(int j=1;j<i;j++){
dp[1][i]=min(dp[1][i],dp[1][j]+dp[j+1][i]);
}
}
}
printf("%lld\n",dp[1][n]);
}
return 0;
}再拓展小小粉刷匠
链接：https://ac.nowcoder.com/acm/problem/16129
来源：牛客网
小小粉刷匠
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
"lalala,我是一个快乐的粉刷匠",小名一边快活地唱着歌,一边开心地刷着墙",兴致突然被打断,"小名,你今天如果刷不完这一栋楼的墙，那么你就等着被炒鱿鱼吧",老板声嘶力竭的吼着。苦恼的小名因为不想被炒鱿鱼,所以希望尽量快地刷完墙,由于他本人的数学基础很差,他现在请你来帮助他计算最少完成每一堵墙需要刷多少次。每一面墙有n个段,对于每个段指定一个目标颜色ci。刚开始的时候所有的墙壁为白色,我们现在有一个刷子,刷子长度为k,刷子每次可以选择一种颜色,然后选择段数为(1～k)连续的墙段刷成选择的一种颜色。我们现在想要知道，为了把墙变成目标颜色，最少刷多少次(保证指定的目标颜色一定不为白色)。
输入描述:
对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,1<=k<=50,k<n),表示墙的长度为n,刷子的长度为k。第二行输入n个整数(c1c2...cn),(1<=ci<=256),表示对于墙的每一段指定的颜色。
输出描述:
输出一个数,表示小名最少刷多少次。
示例1
输入
复制
3 3
1 2 1
输出
复制
2
示例2
输入
复制
5 4
5 4 3 3 4
输出
复制
3
题意：就是再前两个题的基础上多了个刷子长度的限制，
思路：主要思想与前面两个一样，空串刷成目标串，因为有长度限制所以我们要考虑长度的限制，上一个题没有刷子的限制：所以长度随意直接不用管长度：
for(int i=1; i<=n; i++) {
if(str[i]==s[i])///相同位置相同
dp[1][i]=dp[1][i-1];
else {
for(int j=1; j<i; j++) {
dp[1][i]=min(dp[1][i],dp[1][j]+dp[j+1][i]);
}
}
}直接枚举右端点，确定左端点。
而这个题需要考虑长度：
for(int len=m+1;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
dp[i][j]=maxn;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}三个题同出一脉就是刷字符串，基础就是从空串刷成目标串，再按要求进行下一步
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=1e9+7;
const int maxn=2e5+7;
ll n,m;
ll dp[1010][1010];
ll a[maxn];
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1;i<=n;i++) dp[i][i]=1;///每个点至少需要一次
///空串变成这个串
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
dp[i][j]=maxn;
if(a[i]==a[j]){
dp[i][j]=min(dp[i][j-1],dp[i+1][j]);
}else {
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
///长度为m的限制
for(int len=m+1;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
dp[i][j]=maxn;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
printf("%lld\n",dp[1][n]);
return 0;
}[SCOI2003]字符串折叠
链接：https://ac.nowcoder.com/acm/problem/20238
来源：牛客网
[SCOI2003]字符串折叠
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
折叠的定义如下：
一个字符串可以看成它自身的折叠。记作S = S
X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB
给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。
输入描述:
仅一行，即字符串S，长度保证不超过100。
输出描述:
仅一行，即最短的折叠长度。
示例1
输入
NEERCYESYESYESNEERCYESYESYES
输出
14
题意：给出你长度为N的字符串，让你把连着重复出现的字符串合并。
思路：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=1e9+7;
const int maxn=2e5+7;
ll n,m;
ll dp[210][210];
string str;
bool check(int l,int r,int mid) {
ll x=mid-l+1,y=r-l+1;
if(y%x) return 0;
for(int i=l; i<=r;) {
for(int j=l; j<l+x; j++) {
if(str[i++]!=str[j])return 0;
}
}
return 1;
}
int calc(int len1,int len2){
int mn=len1/len2,sum=0;
while(mn){
mn/=10;
sum++;
}
return sum;
}
int main() {
cin>>str;
n=str.size();
str='#'+str;
for(int i=1; i<=n; i++) dp[i][i]= 1;
for(int len=2; len<=n; len++) {
for(int i=1; i<=n-len+1; i++) {
int j=i+len-1;
dp[i][j]=len;
for(int k=i; k<=j; k++) {
if(check(i,j,k)) {
dp[i][j]=min(dp[i][j],dp[i][k]+2+calc(len,k-i+1));
} else {
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
投递牛客等公司10个岗位 >
华为公司氛围 472人发布