思路

首先将乐谱抽象为一个序列(note_id,Vol)，表示以Vol的音量按了钢琴上编号为note_id的琴键。注意这个note_id应该用唯一的编号。
将问题分为两部分：音量代价与音符代价。这两部分的代价计算是分开的。
音量代价：只有在按音符时音量与当前音量不同时计算代价。注意默认音量是100。
音符代价：可以使用动态规划计算。dp[x][y]表示按完前x个音符，当前音阶为y的最小代价。直接按照题目所给信息转移即可。也可以使用最短路。
时间复杂度：O(n88)

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int n,tot,ans,vol,o,dp[100005][10];
pair<int, int> a[100005];
char s[100005];
void init()
{
 tot=ans=0;
 o=4,vol=100;
 for(int i=0;i<=n+3;i++) 
  for(int j=0;j<=8;j++) 
   dp[i][j]=inf;
 dp[0][4]=0;
}
bool note(int i)
{
 return s[i]>='A'&&s[i]<='G';
}
int trans(int x,int y)
{
 return min(abs(x-y),2);
}
int get(int i)
{
 if(s[i]=='C'&&s[i+1]=='-')
  return 0;
 if(s[i]=='C'&&s[i+1]=='+'||s[i]=='D'&&s[i+1]=='-') 
  return 2;
 if(s[i]=='D'&&s[i+1]=='+'||s[i]=='E'&&s[i+1]=='-') 
  return 4;
 if(s[i]=='E'&&s[i+1]=='+') 
  return 6;
 if(s[i]=='F'&&s[i+1]=='-') 
  return 5;
 if(s[i]=='F'&&s[i+1]=='+'||s[i]=='G'&&s[i+1]=='-') 
  return 7;
 if(s[i]=='G'&&s[i+1]=='+'||s[i]=='A'&&s[i+1]=='-') 
  return 9;
 if(s[i]=='A'&&s[i+1]=='+'||s[i]=='B'&&s[i+1]=='-') 
  return 11;
 if(s[i]=='B'&&s[i+1]=='+') 
  return 13;
 if(s[i]=='C') 
  return 1;
 if(s[i]=='D') 
  return 3;
 if(s[i]=='E') 
  return 5;
 if(s[i]=='F') 
  return 6;
 if(s[i]=='G') 
  return 8;
 if(s[i]=='A') 
  return 10;
 if(s[i]=='B') 
  return 12;
}
int main()
{
 while(1)
 {
  scanf("%s",s+1);
  if(s[1]=='*') 
   break;
  n=strlen(s+1);
  init();
  int cnt=0,last=100;
  for(int i=1;i<=n;i++)
  {
   if(note(i)&&last!=vol)
   {
    cnt+=tot;
    last=vol;
    tot=0;
   }
   if(s[i]=='V')
   {
    int len=0,val=0;
    for(int j=i+1;s[j]>='0'&&s[j]<='9';j++) 
     val=val*10+s[j]-'0',len++;
    if(val!=vol) 
     vol=val,tot=len+1;
   }
  }
  tot=0;
  for(int i=1;i<=n;i++)
  {
   if(note(i))
   {
    int id=get(i);
    a[++tot]=make_pair(o,id);
   }
   if(s[i]=='O')
   {
    int val=0;
    for(int j=i+1;s[j]>='0'&&s[j]<='9';j++) 
     val=val*10+s[j]-'0';
    o=val;
   }
   if(s[i]=='>') 
    o++;
   if(o>8) 
    o=8;
   if(s[i]=='<') 
    o--;
   if(o<1) 
    o=1;
  }
  for(int i=1;i<=tot;i++)
  {
   int oc=a[i].first,id=a[i].second;
   if(id==2||id==4||id==7||id==9||id==11)
   {
    for(int j=1;j<=8;j++) 
     dp[i][oc]=min(dp[i][oc],dp[i-1][j]+trans(oc,j)+2);
   }
   if(id==3||id==5||id==6||id==8||id==10)
   {
    for(int j=1;j<=8;j++) 
     dp[i][oc]=min(dp[i][oc],dp[i-1][j]+trans(oc,j)+1);
   }
   if(id==0)
   {
    for(int j=1;j<=8;j++) 
     dp[i][oc]=min(dp[i][oc],dp[i-1][j]+trans(oc,j)+2);
    for(int j=1;j<=8;j++) 
     dp[i][oc-1]=min(dp[i][oc-1],dp[i-1][j]+trans(oc-1,j)+1);
   }
   if(id==1)
   {
    for(int j=1;j<=8;j++) 
     dp[i][oc]=min(dp[i][oc],dp[i-1][j]+trans(oc,j)+1);
    for(int j=1;j<=8;j++) 
     dp[i][oc-1]=min(dp[i][oc-1],dp[i-1][j]+trans(oc-1,j)+2);
   }
   if(id==12)
   {
    for(int j=1;j<=8;j++) 
     dp[i][oc]=min(dp[i][oc],dp[i-1][j]+trans(oc,j)+1);
    for(int j=1;j<=8;j++) 
     dp[i][oc+1]=min(dp[i][oc+1],dp[i-1][j]+trans(oc+1,j)+2);
   }
   if(id==13)
   {
    for(int j=1;j<=8;j++) 
     dp[i][oc]=min(dp[i][oc],dp[i-1][j]+trans(oc,j)+2);
    for(int j=1;j<=8;j++) 
     dp[i][oc+1]=min(dp[i][oc+1],dp[i-1][j]+trans(oc+1,j)+1);
   }
  }
  ans=inf;
  for(int i=1;i<=8;i++) 
   ans=min(ans,dp[tot][i]);
  printf("%d\n",ans+cnt);
 }
 return 0;
}

来源:zr