題目大意： 給兩個字符串A，B，求B串在A串中出現的個數。 解題思路： dp+高精度。 dp[i][j][k]表示串B的前i個在串A的前j個中出現的個數,k表示位數，每一位表示4位十進制的數。 如果save2[i]==save1[j] 則dp[i][j]=dp[i][j-1]+dp[i-1][j-1]; 注意處理初始化的問題。 如果save2[i]!=save1[j] 則dp[i][j]=dp[i][j-1]; 高精度：每一位表示4位十進制的數，如果一位一位的相加的話會超時。 代碼： [cpp] #include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #define eps 1e-6 #define INF (1<<20) #define PI acos(-1.0) using namespace std; char save1[11000],save2[120]; int dp[120][11000][30]; //dp[i][j]表示Zi在Aj中一共有多少個 一位表示4位10000 void add(int i,int j) { int i1=i,j1=j-1,i2=i-1,j2=j-1; for(int k=1;k<=30;k++) { dp[i][j][k+1]+=(dp[i1][j1][k]+dp[i2][j2][k])/10000; //進位 dp[i][j][k]+=(dp[i1][j1][k]+dp[i2][j2][k])%10000; } return ; } int main() { int ca; scanf("%d",&ca); while(ca--) { scanf("%s%s",save1,save2); int len1=strlen(save1),len2=strlen(save2); memset(dp,0,sizeof(dp)); for(int j=0;j<=len1;j++) //注意初始化，用於構建第一種情況 dp[0][j][1]=1; for(int i=1;i<=len2;i++) for(int j=1;j<=len1;j++) { if(save2[i-1]==save1[j-1]) { //dp[i][j]=dp[i][j-1]+dp[i-1][j-1]; //可以從dp[i][j-1]繼承過來，也可以新增dp[i-1][j-1]個 add(i,j); } else { //dp[i][j]=dp[i][j-1]; for(int k=1;k<=30;k++) //直接復制 dp[i][j][k]=dp[i][j-1][k]; } } //printf("%lld\n",dp[len2][len1]); int i; for(i=30;dp[len2][len1][i]==0&&i>=1;i--) //除掉前置零 ; printf("%d",dp[len2][len1][i]); //把第一個處理，不用4位處理。 i--; for(;i>=1;i--) printf("%04d",dp[len2][len1][i]); //注意前置零 putchar('\n'); } return 0; }
