hiho week 60 register

Ended

Participants:587

Verdict:Accepted
Score:100 / 100
Submitted:2015-08-27 17:55:18

Lang:G++

Edit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
  short len1,len2,f[2101][2101];
  int dp0[2101][2101],dp1[2101][2101];                  
int main()
{
  char s1[2101],s2[2101];
  scanf("%s",s1+1);
  scanf("%s",s2+1);
  len1=strlen(s1+1);
  len2=strlen(s2+1);
  for(int i=1;i<=len1;i++)
  {
    for(int j=1;j<=len2;j++)
    {   
      if(s1[i]==s2[j])
        f[i][j]=f[i-1][j-1]+1;
      else
              f[i][j]=0;
      dp1[i][j]=0;
      if(f[i][j]>=3)
      {   
        dp1[i][j]=max(dp1[i][j],dp0[i-3][j-3]+3);
        if(f[i][j]>3)
        dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]+1);
//      dp0[i][j]=max(dp0[i-3][j-3]+3,dp0[i-f[i][j]][j-f[i][j]]+f[i][j]);
      }   
      dp0[i][j]=max(max(dp0[i-1][j],dp0[i][j-1]),dp1[i][j]);
    }   
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX