第2题 牛钢琴

牛的钢琴从左往右有n个按键，第i个按键发出的“音调”是a[i]。

现在奶牛要弹奏一首长度是m个“音调”构成的的歌曲，歌曲的第i个“音调”必须是b[i]。

奶牛只使用1个手指弹琴，手指从第i个按键移动第j个按键需要花费|i-j|秒。

奶牛每次只能使用如下两种操作类型之一：

操作A：假如奶牛手指当前位置是i，那么它可以把手指移动到i-1或者i+1，而且钢琴对应的发出a[i-1]“音调”或者发出a[i+1]“音调”。

操作B：假如奶牛手指当前位置是i，那么它可以把手指移动到j，前提是a[i]等于a[j]。这个操作不会发出“音调”。

注意，任何时候，奶牛的手指移动到的位置范围都是1至N，不能超过钢琴的边界。

任务开始前，奶牛可以把手指放到任意一个按键。

你的任务是计算：奶牛至少需要多少秒完成任务。如果不可能完成任务则输出-1。

输入格式 第1行，两个整数: n和m。 1<=n,m<=300。

第2行，n个音调，第i个音调是a[i], 而且保证a[i]是一个小写英文字母。

第3行，m个音调，第i个音调是b[i], 而且保证b[i]是一个小写英文字母。

输出格式 一个整数。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[305],b[305];
long long f[305][305],c[305],d[305];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=0;i<=304;i++)for(int j=0;j<=304;j++)f[i][j]=1e9;
    long long  s=0,t=b[1];
    for(int i=1;i<=n;i++)if(a[i]==t)f[1][i]=0;
   for(int i=2;i<=m;i++)
   {
   	   for(int j=1;j<=n;j++)
   	   {
   	   	  if(a[j]==b[i])
   	   	  {
   	   	  	    if(b[i-1]==a[j-1])f[i][j]=min(f[i-1][j-1]+1,f[i][j]);
   	   	  	    if(b[i-1]==a[j+1])f[i][j]=min(f[i-1][j+1]+1,f[i][j]);
   	   	  	    if(a[j-1]==b[i-1])
   	   	  	    {
   	   	  	    	for(int k=1;k<=n;k++)
   	   	  	    	{
                            if(j-1!=k)
   	   	  	    		    if(a[k]==b[i-1])
   	   	  	    		    {
   	   	  	    		    	f[i][j]=min(f[i][j],f[i-1][k]+abs(j-1-k)+1);
   	   	  	    		    }
   	   	  	    	}
   	   	  	    }
   	   	  	    else if(a[j+1]==b[i-1])
   	   	  	    {
   	   	  	    	for(int k=1;k<=n;k++)
   	   	  	    	{
   	   	  	    		if(j+1!=k)
   	   	  	    		    if(a[k]==b[i-1])
   	   	  	    		    {
   	   	  	    		    	f[i][j]=min(f[i][j],f[i-1][k]+abs(k-j-1)+1);
   	   	  	    		    }
   	   	  	    	}
   	   	  	    }
      	   	  }
   	   }
   }
   s=1e9;
   for(int i=1;i<=n;i++)
   {
   	 s=min(f[m][i],s);
   }
   if(s==1e9)cout<<-1;
   else cout<<s;
  return 0;
}