squence

考虑静态版本的做法。

只考虑一种单峰，另一种是一样的。

交换次数是对应原数组下标的逆序对个数。

从小到大排序后从两边向中间加数，可以放前面或后面。

贡献是对中间还没有加入的数的逆序对个数，也就是没放的数中 下标比它大的 比 下标比它小的 更多就放前面，否则放后面。

插入一个数，考虑它的影响。

它的下标一定是最大的，肯定放后面，本身不产生贡献。

但在它前面加入且放后面的数贡献+1，且一些放后面的数会改放前面。

对于每个数找到它改放在前面的时刻。

此时没放的数中 下标比它大的 超过 下标比它小的，下标比它小的数不会变化，也就是要找下标比它大的数中第k个值比它大的数的下标。。

写个 bit 维护一下就行了。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3e5+10;
typedef long long ll;

struct bit_array {
    int a[N], lim;
    #define lowbit(x) (x&-x)
    void modify(int pos, int val)
    {
        for(; pos <= lim; pos += lowbit(pos))
            a[pos] += val;
    }
    int query(int pos)
    {
        int ans = 0;
        for(; pos >= 1; pos -= lowbit(pos))
            ans += a[pos];
        return ans;
    }
    void clear()
    {
        memset(a, 0, sizeof(a));
    }
} bit;

int n, tot;
ll ans[N];
int f[N], inv[N];
int a[N], b[N];
vector<int> q[N];


void solve();

int main()
{
    memset(ans, 0x3f, sizeof(ans));
    
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b+1, b+n+1);
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b+1, b+n+1, a[i])-b;
    
    bit.lim = n;
    
    solve();
    for(int i = 1; i <= n; i++)
        a[i] = n-a[i]+1;
    solve();
    
    for(int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
}  

void solve()
{
    bit.clear();
    for(int i = 1; i <= n; i++)
        q[i].clear();
    for(int i = 1; i <= n; i++)
    {
        b[a[i]] = i;
        inv[i] = bit.query(a[i]);
        bit.modify(a[i], 1);
    }
    bit.clear();
    
    for(int i = 1; i <= n; i++)
    {
        int l = b[i], r = n, mid;
        while(l < r)
        {
            mid = (l+r)/2;
            if(bit.query(mid) >= 2*inv[b[i]])
                r = mid;
            else
                l = mid+1;
        }
        q[l].push_back(i);
        bit.modify(b[i], 1);
    }
    bit.clear();
    
    ll v = 0;
    for(int i = 1; i <= n; i++)
    {
        v += bit.query(n)-bit.query(a[i]);
        for(auto j : q[i]) bit.modify(j, -1);
        bit.modify(a[i], 1);
        ans[i] = min(ans[i], v);
    }
}

训练

区间 DP

设 f(l,r)f(l,r) 为完成 [l,r][l,r] 内的任务所消耗的体力点数。

枚举断点，考虑怎么合并两个区间的答案，其实就是求这两个区间之间最多能保留多少圆盘不动。

手玩一下可以发现，最少可以保留 $ save(l,r)= \sum\limits_{j=1}^{m}\left( \min\limits_{i=l}^r{w_{i,j}}\right)$ 个圆盘。

保留一个圆盘可以减少两点体力（放入和取出），所以转移方程就显然了:

f(l,r)=min⁡k=lr−1{f(l,k)+f(k+1,r)−2save(l,r)}f(l,r) = \min_{k=l}^{r-1} \{ f(l,k)+f(k+1,r)-2save(l,r) \}

时间复杂度 O(n3)O(n^3)。

#include <cstring>
#include <iostream>
using namespace std;

const int N = 105;

int n, m;
int w[N][N];
int f[N][N];
int cost[N][N];
int tmp[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> w[i][j];
    for(int l = 1; l <= n; l++)
    {
        memset(tmp, 0x3f, sizeof(tmp));
        for(int r = l; r <= n; r++)
            for(int i = 1; i <= m; i++)
            {
                tmp[i] = min(tmp[i], w[r][i]);
                cost[l][r] += tmp[i];
            }
    }
    memset(f, 0x3f, sizeof(f));
    
    for(int i = 1; i <= n; i++)
        f[i][i] = 2*cost[i][i];
    for(int len = 2; len <= n; len++)
        for(int l = 1; l+len-1 <= n; l++)
        {
            int r = l+len-1;
            for(int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]-2*cost[l][r]);
        }
    cout << f[1][n];
}

糖果

因为蓝莓糖果不能被捡，所以每个人只能捡到比蓝莓糖果更进的糖果，考虑一个贪心，先让第一个人捡最近的，然后让第二个人捡剩下的糖果中最近的，如果有一个人一个糖果也捡不了，就让前面的人做一些妥协，看看能不能让别的人换一个糖果捡，把这个糖果让出来。

这个过程与二分图匹配中匈牙利算法的寻找增广路过程完全一致，所以建个图跑匈牙利算法看看匹配数够不够 nn 就行了。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 2005;

struct point { ll x, y; };
ll dist(point a, point b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }


namespace graph {
    struct edge {
        int to, next;
    } e[N*N];
    int head[N], ecnt = 1;
    int vis[N], dfn;
    int match[N];
    bool find(int x);
    void add_edge(int a, int b);
}
using namespace graph;

int n;
point a[N], lm, b[N];

#define l(i) (i)
#define r(i) (i+n)

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    cin >> lm.x >> lm.y;
    for(int i = 1; i <= n; i++)
        cin >> b[i].x >> b[i].y;
    
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(dist(a[i], b[j]) <= dist(a[i], lm))
                add_edge(l(i), r(j));
    
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        cnt += (dfn++, find(l(i)));
    
    if(cnt == n)
        cout << "POSSIBLE\n";
    else
        cout << "IMPOSSIBLE\n";
}


namespace graph {
    bool find(int x)
    {
        if(vis[x] == dfn)
            return false;
        vis[x] = dfn;
        for(int i = head[x]; i; i = e[i].next)
        {
            if(!match[e[i].to] or find(match[e[i].to]))
            {
                match[e[i].to] = x;
                return true;
            }
        }
        return false;
    }
    void add_edge(int a, int b)
    {
        e[++ecnt] = {b, head[a]}; head[a] = ecnt;
    }
}