其实就是个大模拟。首先对输入的串进行处理，把所有的命令分开，并把连续的停顿合并。为了方便，定义一个时间单位为全音符的\(\frac 1{128}\)，这样所有命令的持续时间都是整数个时间单位。然后就可以dp了，\(dp_{i,j,k}\)表示处理到第i个命令，当前八度为j，当前默认时长为k的最优解长度。音量不需要记录，因为音量操作占用的总长度是固定的，只有音符音量改变的时候才需要用一次。dp的时候需要记录路径，因为是要构造方案的。转移情况比较多，但是都不难想。如果下一个命令准备填L，则转移的时候需要进一步枚举设置成的新的默认长度(一共8种)。需要对任意长度的音符和停顿预处理出在j和k固定的情况下的最短表示。有一个问题是连续的停顿长度可能达到\(128n\)个时间单位，不可能预处理到那么长的。当连续的停顿很长的时候，一定存在一种最优解满足在这些停顿中靠前的某个位置把默认时长设置成了全音符，然后后面填上一堆R，这样是最省空间的。可以猜一个阈值，比如2000，在连续停顿很长的时候把前2000个和后2000个拿出来单独用dp预处理，中间的部分则全填成R。
时间复杂度\(O(8^3n)\)，常数略大。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
const int inf=1000000000;
struct node
{
pii nn;
int oo,ll,vv;
node(pii _n=mpr(0,0),int _o=0,int _l=0,int _v=0){nn=_n;oo=_o;ll=_l;vv=_v;}
};
string s,pat="CDEFGAB",f[2010][10][10];
char c[100010];
vector <node> v,vv;
int dp[100010][10][10],imp[200];
pair <pii,int> lst[100010][10][10];
string lsts[100010][10][10];
int getNid(char c){rep(i,pat.size()) if(pat[i]==c) return i;return 114514;}
string getNote(pii note,int len,int curlen)
{
string ret="";ret.pb(pat[note.fi]);
if(note.se==0) ret.pb('-');else if(note.se==2) ret.pb('+');
if(curlen==len) return ret;
int good=0;rep(i,8) if((1<<i)<=len) good=i;
good=(1<<good);
if(curlen!=good) ret+=to_string(128/good);
LL ori=good;
while(good<len)
{
good+=ori/2;ori/=2;
ret.pb('.');
}
return ret;
}
void upd(int i,int j,int k,int ii,int jj,int kk,string tmp)
{
if(dp[i][j][k]>tmp.size()+dp[ii][jj][kk])
{
dp[i][j][k]=tmp.size()+dp[ii][jj][kk];
lst[i][j][k]=mpr(mpr(ii,jj),kk);
lsts[i][j][k]=tmp;
}
}
void chmin(string &x,string y){if(x=="-"||x.size()>y.size()) x=y;}
int main()
{
rep(i,8) imp[1<<i]=i;
rep(i,2008) rep(j,10) rep(k,10) f[i][j][k]="-";
rep(i,8) f[0][i][i]="";
rep(i,2001) rep(j,8) rep(k,8) if(f[i][j][k]!="-")
{
rep(p,8)
{
int bas=(1<<p);
string bk="";
int ori=bas;
rep(r,p+1)
{
if(i+bas<=2000) chmin(f[i+bas][j][p],f[i][j][k]+"L"+to_string(128/(1<<p))+"R"+bk);
bas+=(ori>>1);ori/=2;bk.pb('.');
}
}
rep(p,8)
{
int bas=(1<<p);
string bk="";
int ori=bas;
rep(r,p+1)
{
if(i+bas<=2000) chmin(f[i+bas][j][k],f[i][j][k]+"R"+(p==k ? "":to_string(128/(1<<p)))+bk);
bas+=(ori>>1);ori/=2;bk.pb('.');
}
}
}
int tn=0;
while(scanf("%s",c))
{
++tn;
s=c;
if(s=="*") break;
int curo=4,curl=32,curv=100;
v.clear();
rep(i,s.size())
{
if(s[i]=='O')
{
curo=s[i+1]-'0';
++i;
}
else if(s[i]=='<') --curo;
else if(s[i]=='>') ++curo;
else if(s[i]=='L')
{
int val=0;
while(i+1<s.size()&&isdigit(s[i+1])) val=val*10+s[++i]-'0';
val=128/val;
curl=val;
}
else if(s[i]=='V')
{
int val=0;
while(i+1<s.size()&&isdigit(s[i+1])) val=val*10+s[++i]-'0';
curv=val;
}
else if(s[i]!='R')
{
pii N=mpr(getNid(s[i]),1);
if(i+1<s.size()&&s[i+1]=='-') N.se=0,++i;
else if(i+1<s.size()&&s[i+1]=='+') N.se=2,++i;
if(N==mpr(2,2)) N=mpr(3,1);else if(N==mpr(3,0)) N=mpr(2,1);
int L=curl;
if(i+1<s.size()&&isdigit(s[i+1]))
{
L=0;
while(i+1<s.size()&&isdigit(s[i+1])) L=L*10+s[++i]-'0';
L=128/L;
}
int ori=L;
while(i+1<s.size()&&s[i+1]=='.') ++i,L+=ori/2,ori/=2;
v.pb(node(N,curo,L,curv));
}
else
{
int L=curl;
if(i+1<s.size()&&isdigit(s[i+1]))
{
L=0;
while(i+1<s.size()&&isdigit(s[i+1])) L=L*10+s[++i]-'0';
L=128/L;
}
int ori=L;
while(i+1<s.size()&&s[i+1]=='.') ++i,L+=ori/2,ori/=2;
v.pb(node(mpr(-1,0),0,L,(v.size()==0 ? 100:v.back().vv)));
}
}
vv.clear();
rep(i,v.size())
{
if(v[i].nn.fi>-1) vv.pb(v[i]);
else
{
int p=i,tot=v[i].ll;
while(p+1<v.size()&&v[p+1].nn.fi==-1) tot+=v[++p].ll;
vv.pb(node(mpr(-1,0),0,tot,v[i].vv));
i=p;
}
}
v=vv;
rep(i,v.size()+3) rep(j,10) rep(k,10) dp[i][j][k]=inf;
dp[0][5][4]=0;
rep(i,v.size()) rep(j,8) repn(k,8) if(dp[i][j][k]<inf)
{
if(v[i].nn.fi>-1)
{
int preV=(i==0 ? 100:v[i-1].vv);
string addV="";
if(preV!=v[i].vv) addV="V"+to_string(v[i].vv);
vector <node> nns=vector <node>{v[i]};
if(v[i].nn==mpr(0,0)&&v[i].oo>1) nns.pb(node(mpr(6,1),v[i].oo-1,v[i].ll,v[i].vv));
else if(v[i].nn==mpr(6,2)&&v[i].oo<8) nns.pb(node(mpr(0,1),v[i].oo+1,v[i].ll,v[i].vv));
else if(v[i].nn==mpr(0,1)&&v[i].oo>1) nns.pb(node(mpr(6,2),v[i].oo-1,v[i].ll,v[i].vv));
else if(v[i].nn==mpr(6,1)&&v[i].oo<8) nns.pb(node(mpr(0,0),v[i].oo+1,v[i].ll,v[i].vv));
rep(p,nns.size())
{
node nxt=nns[p];
string add=addV;
if(nxt.oo==k-1) add.pb('<');
else if(nxt.oo==k+1) add.pb('>');
else if(nxt.oo!=k) add+="O"+to_string(nxt.oo);
string sv=add;
{
int hi=0;rep(r,8) if((nxt.ll&(1<<r))>0) hi=r;
hi=(1<<hi);
add+="L"+to_string(128/hi)+getNote(nxt.nn,nxt.ll,hi);
upd(i+1,imp[hi],nxt.oo,i,j,k,add);
}
add=sv;
{
add+=getNote(nxt.nn,nxt.ll,1<<j);
upd(i+1,j,nxt.oo,i,j,k,add);
}
}
}
else
{
int len=v[i].ll;
string add="";while(len>2000) len-=128,add.pb('R');
rep(ed,8)
{
string tmp=f[len][j][ed];
if(tmp=="-") continue;
if(!add.empty())
{
int pre=0;
if(j==7);
else rep(p,tmp.size()-1) if(tmp[p]=='L'&&tmp[p+1]=='1'&&(p+2>=tmp.size()|| !isdigit(tmp[p+2])))
{
pre=p+2;
break;
}
string tmpp=tmp.substr(0,pre)+add+tmp.substr(pre);
tmp=tmpp;
}
upd(i+1,ed,k,i,j,k,tmp);
}
}
}
int opt=inf,i,j,k;
rep(ii,8) repn(jj,8) if(dp[v.size()][ii][jj]<opt) opt=dp[v.size()][ii][jj],i=v.size(),j=ii,k=jj;
string ans="";
while(i>0)
{
for(int ii=(int)(lsts[i][j][k].size())-1;ii>=0;--ii) ans.pb(lsts[i][j][k][ii]);
pair <pii,int> tmp=lst[i][j][k];i=tmp.fi.fi;j=tmp.fi.se;k=tmp.se;
}
reverse(ans.begin(),ans.end());
printf("%s\n",ans.c_str());
}
return 0;
}