洛谷P2679 子串 [noip2015] dp
2024-08-26 13:25:58
正解:dp
解题报告:
感觉是道dp好题啊,所以就写了个题解
代码实现难度低,思维难度大,像我这种思维僵化傻逼选手只想到了爆搜+组合数学...
其实是道很妙的dp题!好趴也没有多妙主要大概是妙在想到了dp?具体实现很普通的
然后代码没什么要解释的鸭,真的不难,主要觉得题目出得还是挺好的趴,像我这种傻逼根本想不到是dp的鸭...然后实在是想放上来就放上来了
具体实现随便说点儿趴
就f[i][j][k]:A串扫到i B串扫到j 有k个空格 然后这里会发现有俩问题
1)因为f存的是个和我并不知道有多少是上一位匹配上的也就不知道上一个相等的那个位置和这一位之间有没有断电
2)ijl乘起来太大了会MLE掉
解决方法对应也是俩
1)再开个辅助数组g[i][j][k]表示是正儿八经这一位匹配上的
2)可以发现每次转移时i只和上一个i有关,滚动数组处理掉就好
over
#include<bits/stdc++.h> using namespace std; #define ll long long #define rp(i,x,y) for(register ll i=x;i<=y;++i) #define my(i,x,y) for(register ll i=x;i>=y;--i) ; ll n,m,cjk,f[][][],g[][][]; ; string a,b; inline ll read() { ;; '))ch=getchar(); ,ch=getchar(); )+(x<<)+(ch^'),ch=getchar(); return y?x:-x; } int main() { string s; n=read();m=read();cjk=read();cin>>a>>b;f[][][]=;a=' '+a;b=' '+b; rp(i,,n) { f[now][][]=; rp(j,,m) { rp(k,,cjk) { ][j-][k-]+g[now^][j-][k])%mod;//g:可以从之前的f转移来,就必有空格本来没空格也强行当有 也可以从上一位的g转移来,就中间没有空格 ; f[now][j][k]=(f[now^][j][k]+g[now][j][k])%mod; } } now^=; } printf(][m][cjk]); ; }
反正我就是觉得这题很好qwq
最新文章
- 基于.NET的CAD二次开发学习笔记二:AutoCAD .NET中的对象
- 浅谈sql中的in与not in,exists与not exists的区别
- [转]MySQL Explain详解
- RPC、SQL、NFS属于OSI的哪一层
- 【BZOJ】【2753】【SCOI2012】滑雪与时间胶囊
- CentOS 7 之安装Mono&;MonoDevelop
- Servlet过滤器——仿盗链过滤器
- PHP的线程安全与非线程(NTS)安全版本的区别
- Cable master
- 服务器 隐藏php版本,nginx版本号等
- 快速学习 javascript
- hive中,动态添加map和reduce的大小,以增加并行度
- 将爬取的数据保存到mysql中
- vim自动安装插件Vundle
- java实现按中文首字母排序的方式
- HDU - 5157 :Harry and magic string (回文树,求多少对不相交的回文串)
- Windows 7系统垃圾清理自写程序
- 开源大数据技术专场(下午):Databircks、Intel、阿里、梨视频的技术实践
- Http缓存知识;HTTPS, HTTP2相关知识;百度统计和即时线上客服。
- 深入理解 flex 布局以及计算_Flexbox, Layout