LOJ 2172 "FJOI 2016"모든 공통 하위 시퀀스 질문 - 시퀀스 로봇
두 개의 서열 자동기에서 동시에 걸어가면서 이렇게 수색하다.
먼저 사전순이 작은 문자를 검색하면서 출력하면 사전순으로 정렬된다.
방안 수가 많은데 높은 정밀도가 필요합니까?공간이 매우 작아서 위치를 눌러야 한다.1e9의 20명은 딱 충분하다.
n*n의 DP 그룹을 열지 않고 나타나는 상태에 위치를 지정하고 3e6의 DP 그룹을 열면 공간을 만들 수 있습니다.
#include
#include
#include
#define ll long long
using namespace std;
const int N=3015,K=60;
int n,m,c[N][K],d[N][K],lst[K];
char a[N],b[N];
int Id(char ch)
{
if(ch<='Z')return ch-'A';
return ch-'a'+26;
}
char Id2(int k)
{
if(k<26)return k+'A';
return k-26+'a';
}
namespace S1{
int ans,top; char s[N];
void dfs(int p0,int p1)
{
printf("%s
",s+1); ans++;
for(int i=0;i<52;i++)
if(c[p0][i]<=n&&d[p1][i]<=m)
{
s[++top]=Id2(i);
dfs(c[p0][i],d[p1][i]);
s[top]=s[top+1];top--;
}
}
void solve()
{dfs(0,0); printf("%d
",ans);}
}
namespace S2{
const int M=3e6,bs=1e9;
int tot; int dy[N][N];
struct Node{
int a[20];//
void Inc(int k)
{
a[1]+=k;
for(int i=1;i<=a[0];i++)
if(a[i]>=bs)a[i]-=bs,a[i+1]++;
while(a[a[0]+1])a[0]++;
}
void Inc(Node k)
{
int lm=max(a[0],k.a[0]);
for(int i=1;i<=lm;i++)
{
a[i]+=k.a[i];
if(a[i]>=bs)a[i+1]+=a[i]/bs,a[i]%=bs;
}
while(a[a[0]+1])a[0]++;
}
void print()
{
printf("%d",a[a[0]]);
for(int i=a[0]-1;i;i--)
printf("%09d",a[i]);puts("");
}
}dp[M];
int dfs(int p0,int p1)
{
if(dy[p0][p1])return dy[p0][p1];
int cr=++tot; dy[p0][p1]=cr; dp[cr].Inc(1);
for(int i=0,x,y;i<52;i++)
if((x=c[p0][i])<=n&&(y=d[p1][i])<=m)
{
int v=dfs(x,y); dp[cr].Inc(dp[v]);
}
return cr;
}
void solve()
{ int v=dfs(0,0); dp[v].print();}
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",a+1); scanf("%s",b+1);
for(int i=0;i<52;i++)lst[i]=n+1;
for(int i=n;i>=0;i--)
{
for(int j=0;j<52;j++)
c[i][j]=lst[j];
lst[Id(a[i])]=i;
}
for(int i=0;i<52;i++)lst[i]=m+1;
for(int i=m;i>=0;i--)
{
for(int j=0;j<52;j++)
d[i][j]=lst[j];
lst[Id(b[i])]=i;
}
int op;scanf("%d",&op);
if(op==1)S1::solve();
else S2::solve();
return 0;
}
전재 대상:https://www.cnblogs.com/Narh/p/10797933.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.