牛客练习赛85 B 音乐家的曲调 DP 尺取
2021/6/25 23:27:05
本文主要是介绍牛客练习赛85 B 音乐家的曲调 DP 尺取,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
题意:
给出一个全由小写字母组成的字符串,让你找出三个区间,这三个区间不能重合,并且每个区间内1,每个字母出现的顺序不能超过m次,找出使得这三个区间长度之和最大的情况
题解:
1,如何找出最长的一个区间使得每个字母出现的次数不超过m次
用一个数组记录26个字母分别出现多少次,再用一个指针记录在当前位置下,在保证每个字母出现次数都不超过m的条件下,区间往左最长能有多长
当遍历到第i位,某个字母出现了m+1次时,记此时上述指针指向的位置是k,则令endp[k]=i-1,然后k++
i遍历完成整个字符串后,令当前k右边所有字符的right_broad都为字符串最末一个字符的位置
endp[i]-i+1中的最大值就是最长的区间
2,如何找出三个区间使得总的区间和最大
从后向前dp
第一次dp寻找在仅保留第i位及其右边的字符的情况下,最长的符合条件的区间
dp1[i]=max(dp1[i+1],endp[i]-i+1);
第二次dp寻找在仅保留第i位及其右边的字符的情况下,两个符合条件的区间的长度和的最大值
dp2[i]=max(dp2[i+1],endp[i]-i+1+dp1[endp[i]+1]);
这个状态转移公式解释一下,从第i位起的那个符合条件的区间要全取走,然后就剩下了从第endp[i]+1位起右边的剩余字符了,这时候dp1里面存储的就是答案
第三次dp同理
dp3[i]=max(dp3[i+1],endp[i]-i+1+dp2[endp[i]+1]);
#include<iostream> #include<string> #include<queue> /*struct Point{ int id; char c; } Point point(int a,char b){ Point tmp; tmp.id=a; tmp.c=b; return tmp; };*/ using namespace std; int alphabet[200]; int endp[10000007]; int dp1[10000007],dp2[10000007],dp3[10000007]; string s; int main(){ int n,m; cin>>n>>m; cin>>s; int l=n; queue<int> que[200]; for(int i=0;i<l;i++){ if(alphabet[s[i]]==m){ endp[que[s[i]].front()]=i-1; alphabet[s[i]]--; que[s[i]].pop(); } alphabet[s[i]]++; que[s[i]].push(i); } for(int i='a';i<='z';i++){ while(!que[i].empty()){ endp[que[i].front()]=l-1; que[i].pop(); } } for(int i=l-2;i>=0;i--){ endp[i]=min(endp[i],endp[i+1]); } /*for(int i=0;i<l;i++){ cout<<endp[i]<<" "; } cout<<endl;*/ //int dp1=l-1,dp2=l-1,dp3=l-1; for(int i=l-1;i>=0;i--){ dp1[i]=max(dp1[i+1],endp[i]-i+1); } for(int i=l-1;i>=0;i--){ dp2[i]=max(dp2[i+1],endp[i]-i+1+dp1[endp[i]+1]); } for(int i=l-1;i>=0;i--){ dp3[i]=max(dp3[i+1],endp[i]-i+1+dp2[endp[i]+1]); } cout<<dp3[0]<<endl; return 0; }
这篇关于牛客练习赛85 B 音乐家的曲调 DP 尺取的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了