美团杯2020 查查查乐乐 dp数据结构与算法weixin44491423的博客-

**题目链接：**https://uoj.ac/problem/519

**题目背景：**美团杯的签到题，蒟蒻的我不会做QAQ。。。

题目大意：
给定一个字符串s，只含有字符‘x’和‘l’，你可以将’x’变成’l’，也可以‘l’变成’x’，问你字符串删去任意个字符都不会出现子串’xxxll’，至少需要变换几次。

解题思路：
小数据：n<=10,暴力枚举即可。
大数据：n<=100,比赛的时候想的是贪心，但是‘x’变‘l’会对之前的串产生影响，’l’变‘x’会对之后的串产生影响。所以并不能把问题的最优解转化为子问题的最优解，贪心是不行的。贪心不行的话，就可以想到动态规划了。
我们可以先看有哪几种串是满足条件的
1.空串。前缀是0。
2.‘x’,‘xl’,‘xll’…。前缀是1。
3.‘xx’,‘xlx’,‘xxll’…。前缀是2。
4.‘xxx’,‘xxlx’,‘xlxx’…。前缀是3。
5.‘xxxl’,‘xxlxl’,‘xlxxl’…。前缀是4。
只有以上情况是满足条件的。
那么我们可以设dp方程为dp[i][l],即只修改前i个元素，使前缀为l，最少需要多少次。
那么答案就是dp[n][0]~dp[n][4]中最小的那个。
那么dp的转移方程是什么呢。
分成两种情况
1.s1[i]是’xxxll’的第l+1个元素

dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);//不修改前缀+1 dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1);//修改次数+1

2.s1[i]不是’xxxll’的第l+1个元素（直接转移，不用修改）

dp[i+1][j]=min(dp[i+1][j],dp[i][j]);

完整AC代码：

#include <iostream> #include <stdio.h> #include <cstring> using namespace std; const int maxn=105; const int inf=10000; int T; char s1[maxn],s2[maxn]; int dp[maxn][6]; int main() { scanf("%d",&T);     s2[1]='x',s2[2]='x',s2[3]='x',s2[4]='l',s2[5]='l'; while(T--) { scanf("%s",s1); memset(dp,inf,sizeof(dp)); int n=strlen(s1);         dp[0][0]=0; for(int i=0;i<n;i++) for(int j=0;j<5;j++) { if(dp[i][j]<inf) { if(s2[j+1]==s1[i]) {                     dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);                     dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1); } else                 dp[i+1][j]=min(dp[i+1][j],dp[i][j]); } } int ans=inf; for(int i=0;i<5;i++)         ans=min(ans,dp[n][i]); printf("%dn",ans); } return 0; }