https://codeforces.com/contest/2051/problem/G
发现n很小，考虑状压dp。
那么状态表示一般就是，dp[i][mask]。最后一个安排的蛇是i，已经安排的蛇二进制表示为mask。至于表示什么，，先顺下思路，总之表示的是最优安排的某个性质。
那么状态转移一般就是枚举下一个点（或者因为写法原因枚举上一个点）。那么考虑答案性质，下一个蛇的位置尽量小。
怎么样是尽量小呢，发现要求是当前点的”增长曲线”，全程在下一个点的”缩小曲线”下方。那么假设他们初始时刻在同一个点，求一下当前点在所有时刻，比下一个点高出的最大距离gap。那么如果要求当前点与下一个点不相遇，下一个点的初始位置必须比当前点的初始位置高出gap+1。
那么状态表示也很合理能得出，为：最后一个安排的蛇是i，已经安排的为mask的方案中，最后一个蛇的位置的最小值。
btw最终的答案还要加上最后一条蛇enlarg的次数。

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int n,q;
vector<int> id,ch;
int getDist(int s,int t){
    int res = 0;
    int gap = 0;
    for(int i=0;i<q;i++){
        if(id[i]==s){
            gap += ch[i] > 0;
        }else if(id[i]==t){
            gap -= ch[i] < 0;
        }
        res = max(res,gap);
    }
    return res + 1;

}

void solve(){
    cin>>n>>q;
    id.resize(q);
    ch.resize(q);
    for(int i=0;i<q;i++){
        char c;
        cin>>id[i]>>c; 
        id[i]--;
        ch[i] = c == '+' ? 1 : -1;
    }
    vector<vector<int>> minDist(n, vector<int>(n, 1e9+10));
    vector<int> len(n,0);
    for(int i=0;i<q;i++){
        if(ch[i]==1)
            len[id[i]]++;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            minDist[i][j] = getDist(i,j);

    vector<vector<int>> dp(n,vector<int>((1<<n),1e9+10));
    for(int i=0;i<n;i++){
        dp[i][1<<i] = 1;
    }
    for(int state = 1;state < (1<<n);state++){
        for(int i = 0;i<n;i++){
            if((state & (1<<i)) == 0) continue;
            if(dp[i][state] == 1e9+10) continue;

            for(int j = 0;j<n;j++){
                if(i==j) continue; 
                if((state & (1<<j)) == 1) continue;
                int nstate = state | (1<<j);
                dp[j][nstate] = min(dp[j][nstate],dp[i][state] + minDist[i][j] );
            }
        }
    }
    int ans = 1e9+10;
    for(int i=0;i<n;i++){
        ans = min(ans,dp[i][(1<<n)-1] + len[i]);
    }
    cout<<ans<<endl;
}

int main(){     
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}