fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define max3(a,b,c) max(max(a,b),c)
  4. #define min3(a,b,c) min(min(a,b),c)
  5. #define PI acos(-1.0)
  6. #define LL long long
  7. #define INF_MAX 2147483647
  8. #define INF_MIN -2147483647
  9. #define MX 1000005
  10. #define MOD 1000000007
  11. int dp[5010][5010];
  12. int way[5010][5010];
  13. int main()
  14. {
  15.     //freopen("a.in", "r", stdin);
  16.     //freopen("a.out", "w", stdout);
  17.     //string s1,s2;
  18.     char s1[33],s2[33];
  19.     int test,t=1;
  20.     //cin>>test;
  21.     scanf("%d",&test);
  22.     getchar();
  23.     while(test--)
  24.     {
  25.         //getline(cin,s1);
  26.         //getline(cin,s2);
  27.         gets(s1);
  28.         gets(s2);
  29.         //scanf("%s",&s1);
  30.         //scanf("%s",&s2);
  31.        // int len1=s1.length();
  32.         //int len2=s2.length();
  33.         int len1=strlen(s1);
  34.         int len2=strlen(s2);
  35.         memset(dp,0,sizeof(dp));
  36.         memset(way,0,sizeof(way));
  37.         for (int i = 0; i <= len1; i++)  way[i][0] = 1;
  38.         for (int j = 0; j <= len2; j++) way[0][j] = 1;
  39.         for(int i=1; i<=len1; i++)
  40.         {
  41.             for(int j=1; j<=len2; j++)
  42.             {
  43.                 if(s1[i-1]==s2[j-1])
  44.                 {
  45.                     dp[i][j]=dp[i-1][j-1]+1;
  46.                     way[i][j]=way[i-1][j-1];
  47.                 }
  48.                 else
  49.                 {
  50.                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  51.                     way[i][j]=0;
  52.                     if(dp[i][j]==dp[i-1][j])
  53.                     {
  54.                         way[i][j]+=way[i-1][j];
  55.                     }
  56.                     if(dp[i][j]==dp[i][j-1])
  57.                     {
  58.                         way[i][j]+=way[i][j-1];
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.         // cout<<dp[len1][len2]<<endl;
  64.         printf("Case #%d: %d %d\n",t++,(len1+len2)-dp[len1][len2],way[len1][len2]);
  65.     }
  66. }
  67.  
  68.  
  69.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
3
ABAAXGF
AABXFGA
ABA
BXA
AABBA
BBABAA
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:27:16: error: 'gets' was not declared in this scope
         gets(s1);
                ^
stdout
copy 
Standard output is empty
https://ideone.com/6Wo9sx
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!