2022/4/3 DP专场总结
2022/4/3 23:20:13
本文主要是介绍2022/4/3 DP专场总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
虽然现在是清明节假期期间,但架不住竞赛集训啊……
懒得一道一道贴了,所以:比赛链接
A.饭卡
-
一道极其浅显易懂易做的线性DP;
-
虽然但是,还是由于没有取 \(|\) 而吃了两发罚时;
AC code
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define re register inline int read(){ int s=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ s=s*10+int(ch-'0'); ch=getchar(); } return s*f; } const int x=1000; int n,m; int p[1005]; int f[2005]; int main(){ while(n=read()){ if(!n) return 0; for(re int i=1;i<=n;++i) p[i]=read(); sort(p+1,p+n+1); m=read(); memset(f,0,sizeof(f)); f[m+x]=1; int ans=m; for(re int i=1;i<=n;++i){ for(re int j=5;j<=m;++j){ f[j-p[i]+x]=f[j-p[i]+x]|(1&f[j+x]); } } for(re int i=x-p[n];i<=m+x;++i){ if(f[i]){ ans=i-x; break; } } printf("%d\n",ans); } return 0; }
B.Cheapest Palindrome
-
是一道同样浅显易懂的区间DP;
-
然而考场上并没有做;
-
考虑枚举区间两个端点 \(s_{st},s_e\) 的状态:
- 如果 \(s_{st}=s_e\),说明是对称的,则不需要修改,有 \(f_{st,e}=min(f_{st,e},f_{st+1,e-1})\);
- 其他的可能:\(f_{st,e}=min(f_{st+1,e}+price_{st},f_{st,e-1}+price_e)\),即分别修改 \(st\) 或 \(e\) 时的最小花费;
-
可以证明,删除和插入效果是等价的,因此 \(price_i\) 取两个花费中的最小值即可;
AC code
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<ios> using namespace std; int n,m; string s; int v[30][3]; int p[30]; int f[3005][3005]; int main(){ cin>>n>>m; cin>>s; char ch; for(int i=1;i<=n;++i){ cin>>ch; cin>>v[int(ch-'a')][0]>>v[int(ch-'a')][1]; } for(int i=0;i<=26;++i) p[i]=min(v[i][0],v[i][1]); memset(f,0x3f,sizeof(f)); for(int i=0;i<=s.size();++i) for(int j=i;j>-1;--j) f[i][j]=0; for(int l=1;l<=s.size();++l){ for(int st=1;st+l<=s.size();++st){ int e=st+l; if(st && s[st-1]==s[e-1]) f[st][e]=min(f[st][e],f[st+1][e-1]); f[st][e]=min(f[st][e],f[st+1][e]+p[int(s[st-1]-'a')]); f[st][e]=min(f[st][e],f[st][e-1]+p[int(s[e-1]-'a')]); // printf("%d %d %d\n",st,e,f[st][e]); } } cout<<f[1][s.size()]; return 0; }
这篇关于2022/4/3 DP专场总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性