题解：CF31E TV Game

· · 题解

水动归一道。根据已填入第一个数的数字和已填入第二个数的数字分别的个数设立状态，注意到两个数都只有 n 位，状态转移方程就是从高位到低位模拟填数时的增量，比较从第一个和第二个数少一个数字往上填哪个大。这种做法没有后效性，复杂度为 O(n^2)。记得填数时同时记下值和，同时注意 Python 在本题数据范围下容易出锅。

AC代码

x=int(input());s=list(map(int,input()));from functools import*
@lru_cache#注意 CF 的Python 版本还没有 functools.cache 函数，小心报错
def f(i,j):
    if i+j==0:return[0,'']
    if i>j or i==0:return[-7<<61,'x'*j]#这个地方尤其注意要和 C++ 一样把负无穷开大，不知为何这里会出现负加正得正的现象
    a=f(i,j-1)[:];b=f(i-1,j-1)[:]#这个地方注意浅拷贝问题，因为 Python 的 lru_cache 存储本质上是字典，返回的列表是有真实指针的
    a[0]+=s[j-1]*10**(x-j+i);a[1]+='M';b[0]+=s[j-1]*10**(x-i);b[1]+='H';return max(a,b)
print(f(x,2*x)[1])