【反発原理】wikioi 1778統計共通サブシーケンス個数
タイトルリンク:http://wikioi.com/problem/1778/
分析:
まず,1つのシーケンスしかない場合,繰り返しないサブシーケンスがどれだけあるかをどのように求めるかを考えてみる.明らかにF[I]はこのシーケンスの前Iビットがどれだけ異なるサブシーケンスを持っているかを定義することができ、移行方程式は簡単である.I番目のアルファベットはあるシーケンスの後ろに接続してもよいし、接続しなくてもよいので、自然にF[I]=F[I-1]*2である.これで答えは2^の長さになります.しかし、これは明らかに間違っている.私たちは重い判決を下さなかったからです.
どのように重くするかを知るには、繰り返しシーケンスが発生した原因を知る必要があります.
現在のビットS［I］＝’a’とし、Jを最大のJとする
ここで我々は問題を複雑な状況に拡張することができ,類似の思想があり,遷移方程式を簡単に考えることができ,A[I]=B[J]=C[K]のとき,明らかに
F[I,J,K]=F[I-1,J-1,K-1]*2-F[II-1,JJ-1,KK-1であり、ここでII,JJ,KKはそれぞれ3つのシーケンスがI,J,Kビット前の最もこのビットに近い位置であり、A[I]=A[II],B[J]=B[JJ],C[K]=C[KK]である.この問題は解決されたようですが、プログラムを書くと、マルチシーケンスと単一シーケンスが異なることがわかります!
マルチシーケンスと単一シーケンスの違いは、マルチシーケンスが文字が等しくない場合の遷移を考慮する必要があることです.前の状態を全部移さなければならないし、繰り返すこともできないし、解決できる考えはありますか?
反発原理!!
状態遷移方程式を得ることができます
F[I,J,K]=
F[I-1,J,K]+F[I,J-1,K]+F[I,J,K-1]
-F[I-1,J-1,K]-F[I-1,J,K-1]-F[I,J-1,K-1]
+F[I-1,J-1,K-1].
特にヒント:このような方法は空のシーケンスを含み、明らかに1文字で構成されたシーケンスは空のシーケンスから移行したので、答えを出力するときにこの空のシーケンスを減算する必要があります.また、この問題は高精、圧位を使います.
コード:
分析:
まず,1つのシーケンスしかない場合,繰り返しないサブシーケンスがどれだけあるかをどのように求めるかを考えてみる.明らかにF[I]はこのシーケンスの前Iビットがどれだけ異なるサブシーケンスを持っているかを定義することができ、移行方程式は簡単である.I番目のアルファベットはあるシーケンスの後ろに接続してもよいし、接続しなくてもよいので、自然にF[I]=F[I-1]*2である.これで答えは2^の長さになります.しかし、これは明らかに間違っている.私たちは重い判決を下さなかったからです.
どのように重くするかを知るには、繰り返しシーケンスが発生した原因を知る必要があります.
現在のビットS［I］＝’a’とし、Jを最大のJとする
ここで我々は問題を複雑な状況に拡張することができ,類似の思想があり,遷移方程式を簡単に考えることができ,A[I]=B[J]=C[K]のとき,明らかに
F[I,J,K]=F[I-1,J-1,K-1]*2-F[II-1,JJ-1,KK-1であり、ここでII,JJ,KKはそれぞれ3つのシーケンスがI,J,Kビット前の最もこのビットに近い位置であり、A[I]=A[II],B[J]=B[JJ],C[K]=C[KK]である.この問題は解決されたようですが、プログラムを書くと、マルチシーケンスと単一シーケンスが異なることがわかります!
マルチシーケンスと単一シーケンスの違いは、マルチシーケンスが文字が等しくない場合の遷移を考慮する必要があることです.前の状態を全部移さなければならないし、繰り返すこともできないし、解決できる考えはありますか?
反発原理!!
状態遷移方程式を得ることができます
F[I,J,K]=
F[I-1,J,K]+F[I,J-1,K]+F[I,J,K-1]
-F[I-1,J-1,K]-F[I-1,J,K-1]-F[I,J-1,K-1]
+F[I-1,J-1,K-1].
特にヒント:このような方法は空のシーケンスを含み、明らかに1文字で構成されたシーケンスは空のシーケンスから移行したので、答えを出力するときにこの空のシーケンスを減算する必要があります.また、この問題は高精、圧位を使います.
コード:
#include
#include
#include
#include
#define ff 1000000000
using namespace std;
int n;
struct node
{
int s[10];
} f[151][151][151];
inline void jian( int i, int j, int k, int i1,int j1,int k1 )
{
for (int ji=1;ji<=9;ji++)
{
f[i][j][k].s[ji]-=f[i1][j1][k1].s[ji];
if (f[i][j][k].s[ji]<0)
{
f[i][j][k].s[ji+1]-=1;
f[i][j][k].s[ji]+=ff;
}
}
}
inline void jia( int i, int j, int k, int i1,int j1,int k1,int kk)
{
for (int ji=1;ji<=kk;ji++)
for (int ki=1;ki<=9;ki++)
{
f[i][j][k].s[ki]+=f[i1][j1][k1].s[ki];
if (f[i][j][k].s[ki]>=ff)
{
f[i][j][k].s[ki+1]+=(f[i][j][k].s[ki]/ff);
f[i][j][k].s[ki]%=ff;
}
}
}
int main()
{
string a=" ",b=" ",c=" ",aa,bb,cc;
int i,j,k;
cin>>n;
cin>>aa>>bb>>cc;
a+=aa;b+=bb;c+=cc;
for(i=0;i<=n;++i)
for(j=0;j<=n;++j)
{
f[0][i][j].s[1]=1;
f[i][j][0].s[1]=f[i][0][j].s[1]=f[0][i][j].s[1];
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++)
{
if (a[i]==b[j]&&b[j]==c[k])
{
jia(i,j,k,i-1,j-1,k-1,2);
int ji=i-1; while (a[ji]!=a[i]&&ji>0) ji--;
int jj=j-1; while (b[jj]!=b[j]&&jj>0) jj--;
int jk=k-1; while (c[jk]!=c[k]&&jk>0) jk--;
if(ji>0&&jj>0&&jk>0) jian(i,j,k,ji-1,jj-1,jk-1);
}
else
{
jia(i,j,k,i-1,j,k,1);
jia(i,j,k,i,j-1,k,1);
jia(i,j,k,i,j,k-1,1);
jia(i,j,k,i-1,j-1,k-1,1);
jian(i,j,k,i-1,j-1,k);
jian(i,j,k,i,j-1,k-1);
jian(i,j,k,i-1,j,k-1);
}
}
jian(n,n,n,0,0,0);
int jiji=9; while (f[n][n][n].s[jiji]==0) jiji--;
cout<=1;i--) printf("%.9d",f[n][n][n].s[i]);
return 0;
}