Goodbye world!
NOIP2015复赛提高组成绩
noi 于 13:55 发给 我
NOIP2015复赛提高组成绩
| 姓名 | 编号 | 总分 | magic | message | landlords | stone | substring | transport |
| 500 | 100 | 100 | 100 | 100 | 20 | 80 |
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<sstream>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[205][205][2];
int last_dp[205][205][2];
char a[1005];
char b[205];
const int modo=1000000007;
int main()
{
freopen("substring.in","r",stdin);
freopen("substring.out","w",stdout);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int i;
scanf("%s%s",a,b);
dp[0][0][0]=1;
for (i=0;i<n;i++)
{
int j;
for (j=min(i,m-1);j>=0;j--)
{
int l=min(j,k-1);
int * z=dp[j][l];
int * y=dp[j+1][l];
int * x=dp[j+1][l+1];
for (l=min(j,k-1);l>=0;l--)
{
if (a[i]==b[j])
{
x[1]+=z[0];
if (x[1]>=modo)
{
x[1]-=modo;
}
x[0]+=z[0];
if (x[0]>=modo)
{
x[0]-=modo;
}
y[1]+=z[1];
if (y[1]>=modo)
{
y[1]-=modo;
}
y[0]+=z[1];
if (y[0]>=modo)
{
y[0]-=modo;
}
}
z[1]=0;
z-=2;
y-=2;
x-=2;
}
}
}
printf("%d\n",dp[m][k][0]);
return 0;
}
评论 (0)