【2020NOI.AC省选模拟#9】C. 重复
2024-09-08 19:11:18
题目链接
原题解:
通过计数相同的子序列对个数的方式来计算答案。
设$f(i,j)$为$S$的前$i$和$j$个字符的公共子序列对个数。
当$S_i=S_j$时,$f(i,j)=f(i,j-1)+f(i-1,j)$。
否则,$f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)$。
还可以通过依次将$i$和$j$一次一步地移到下一个配对的字符的位置的方式转移,复杂度为$O(n^2)$。
补充:
$f$数组只能用int而不能用long long,不然会爆空间。
代码(100分):
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define IL inline
#define RG register
using namespace std;
#define RI RG int
#define RC RG char
const int N=1e4; int n,a[N+3],mod; IL bool insigma(RC ch){
return 33<=ch&&ch<=126;
} int f[N+3][N+3]; IL int add(RI x,RI y){
return (x+=y)>=mod?x-=mod:x;
} int main(){
n=0;
for(RC ch=getchar();insigma(ch);ch=getchar())
a[++n]=ch;
scanf("%d",&mod); for(RI i=0;i<=n;i++)
f[0][i]=1;
for(RI i=1;i<=n;i++){
for(RI j=1;j<=n;j++){
f[i][j]=f[i][j-1];
if(a[i]==a[j])
f[i][j]=add(f[i][j],f[i-1][j-1]); } for(RI j=0;j<=n;j++)
f[i][j]=add(f[i][j],f[i-1][j]); } printf("%d",f[n][n]); return 0; }
最新文章
- Python学习感悟
- C编译: 动态连接库 (.so文件)(转摘)
- 推荐一些mac 系统软件
- [Cocos2d-x For WP8]矩形碰撞检测
- Flash Builder 找不到所需的 Adobe Flash Player
- 20160805_CentOS6_控制台切换
- HDU 2152 Fruit
- 安装sysbench遇到找不到库文件的问题
- 逐步搭建Lamp环境之rpm软件包管理
- JBOSS EAP实战(2)-集群、NGINX集成、队列与安全
- 百度地图API开发一——仿照现有测距效果实现测面功能
- Android的ViewPager的学习
- 【译】BERT表示的可解释性分析
- 几种序列化协议(protobuf,xstream,jackjson,jdk,hessian)相关数据对比
- !!代码:baidu地图
- recovery 升级过程执行自定义shell命令
- luogu4181 [USACO18JAN]Rental Service (贪心)
- [开发笔记]-实现winform半透明毛玻璃效果
- struts2中s:select标签的使用
- angularJS的ng-repeat-start