bzoj - 4873

Posted by WildCow on September 21, 2018

[Shoi2017]寿司餐厅

Time Limit: 20MS
Memory Limit: 512 MB

Description

$Kiana​$ 最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上,这家餐厅都会按顺序提供 $n​$ 种寿司,第 $i​$ 种寿司有一个代号 $a_i​$ 和美味度 $d_{i,i}​$,不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,$Kiana​$ 也可以无限次取寿司来吃,但每种寿司每次只能取一份,且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段,即$Kiana​$ 可以一次取走第 $1,2​$ 种寿司各一份,也可以一次取走第 $2,3​$ 种寿司各一份,但不可以一次取走第 $1,3​$ 种寿司。由于餐厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司和鱿鱼寿司一起吃或许会很棒,但和水果寿司一起吃就可能会肚子痛。因此,$Kiana​$ 定义了一个综合美味度 $d_{i,j}(i<j)​$,表示在一次取的寿司中,如果包含了餐厅提供的从第i份到第j份的所有寿司,吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间,所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时,不止一个综合美味度会被累加,比如若 $Kiana​$ 一次取走了第 $1,2,3​$ 种寿司各一份,除了 $d_{1,3}​$ 以外,$d_{1,2},d_{2,3}​$也会被累加进总美味度中。神奇的是,$Kiana​$ 的美食评判标准是有记忆性的,无论是单种寿司的美味度,还是多种寿司组合起来的综合美味度,在计入 $Kiana​$ 的总美味度时都只会被累加一次。比如,若 $Kiana​$ 某一次取走了第 $1,2​$ 种寿司各一份,另一次取走了第 $2,3​$ 种寿司各一份,那么这两次取寿司的总美味度为 $d_{1,1} + d_{2,2} + d_{3,3} + d_{1,2} + d_{2,3}​$ ,其中 $d_{2,2}​$ 只会计算一次。奇怪的是,这家寿司餐厅的收费标准很不同寻常。具体来说,如果 $Kiana​$ 一共吃过了$c(c>0)​$ 种代号为 $x​$ 的寿司,则她需要为这些寿司付出 $mx^2+cx​$元钱,其中 $m​$ 是餐厅给出的一个常数。现在 $Kiana​$ 想知道,在这家餐厅吃寿司,自己能获得的总美味度(包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。由于她不会算,所以希望由你告诉她。

Input

第一行包含两个正整数 $n,m$,分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。 第二行包含 $n$ 个正整数,其中第 $k$ 个数 $a_k$ 表示第 $k$ 份寿司的代号。 接下来 $n$ 行,第 $i$ 行包含 $n-i+1$ 个整数,其中第 $j$ 个数 $d_{i,i+j-1}$ 表示吃掉寿司能获得的相应的美味度,具体含义见问题描述。 $N<=100,Ai<=1000$

Output

输出共一行包含一个正整数,表示Kiana能获得的总美味度减去花费的总钱数的最大值

Sample Input

3 1
2 3 2
5 -10 15
-10 15
15

Sample Output

12

Hint

在这组样例中,餐厅一共提供了 $3$ 份寿司,它们的代号依次为 $a_1=2,a_2=3,a_3=2$,计算价格时的常数 $m = 1$。在保证每次取寿司都能获得新的美味度的前提下,$Kiana$ 一共有 14 种不同的吃寿司方案:

  1. $Kiana$ 一个寿司也不吃,这样她获得的总美味度和花费的总钱数都是 $0$,两者相减也是 $0$;

  2. $Kiana$ 只取 $1$ 次寿司,且只取第 $1$ 个寿司,即她取寿司的情况为 ${[1,1]}$,这样获得的总美味度为 $5$,花费的总钱数为 $1-2^2+1*2 = 6$,两者相减为 $-1$;

  3. $Kiana$ 只取 $1$ 次寿司,且只取第 $2$ 个寿司,即她取寿司的情况为 ${[2,2]}$,这样获得的总美味度为 $-10$,花费的总钱数为 $1-3^2+1*3 = 12$,两者相减为 $-22$;

  4. $Kiana$ 只取 $1$ 次寿司,且只取第 $3$ 个寿司,即她取寿司的情况为 ${[3,3]}$,这样获得的总美味度为15,花费的总钱数为 $12^2+12 = 6$,两者相减为 $9$;

  5. $Kiana$ 只取 $1$ 次寿司,且取第 $1,2$ 个寿司,即她取寿司的情况为 ${[1,2]}$,这样获得的总美味度为 $5+(-10)+(-10) = -15$,花费的总钱数为 $(1-2^2+12)+(1-3^2+13)=18$,两者相减为 $-33$;

  6. $Kiana$ 只取 $1$ 次寿司,且取第 $2,3$ 个寿司,即她取寿司的情况为 ${[2,3]}$,这样获得的总美味度为$(-10)+15+15 = 20$,花费的总钱数为 $(1-2^2+12)+(13^2+1*3)=18$,两者相减为 $2$;

  7. $Kiana$ 只取 $1$次寿司,且取第 $1,2,3$ 个寿司,即她取寿司的情况为 ${[1,3]}$,这样获得的总美味度为 $5+(-10)+15+(-10)+15+15 = 30$,花费的总钱数为 $(12^2+22)+(13^2+13)=20$,两者相减为 $10$。

  8. $Kiana$ 取 $2$ 次寿司,第一次取第 $1$ 个寿司,第二次取第 $2$ 个寿司,即她取寿司的情况为 ${[1,1],[2,2]}$,这样获得的总美味度为 $5+(-10) = -5$,花费的总钱数为 $(12^2+12)+(13^2+13)=18$,两者相减为 $-23$;

  9. $Kiana$ 取 $2$ 次寿司,第一次取第 $1$ 个寿司,第二次取第 $3$ 个寿司,即她取寿司的情况为 ${[1,1],[3,3]}$,这样获得的总美味度为 $5+15 = 20$,花费的总钱数为 $12^2+22=8$,两者相减为 $12$;

  10. $Kiana$ 取2次寿司,第一次取第 $2$ 个寿司,第二次取第 $3$ 个寿司,即她取寿司的情况为 ${[2,2],[3,3]}$,这样获得的总美味度为 $(-10)+15 = 5$,花费的总钱数为 $(12^2+12)+(13^2+13)=18$,两者相减为 $-13$;

  11. $Kiana$ 取 $2$ 次寿司,第一次取第 $1,2$ 个寿司,第二次取第 $3$ 个寿司,即她取寿司的情况为 ${[1,2],[3,3]}$,这样获得的总美味度为 $5+(-10)+(-10)+15 = 0$,花费的总钱数为 $(12^2+22)+(13^2+13)=20$,两者相减为 $-20$;

  12. $Kiana$ 取 $2$ 次寿司,第一次取第 $1$ 个寿司,第二次取第 $2,3$ 个寿司,即她取寿司的情况为 ${[1,1],[2,3]}$,这样获得的总美味度为 $5+(-10)+15+15 = 25$,花费的总钱数为 $(1-22+2-2)+(1-32+1-3)=20$,两者相减为 $5$;

  13. $Kiana$ 取 $2$ 次寿司,第一次取第 $1,2$ 个寿司,第二次取第 $2,3$ 个寿司,即她取寿司的情况为 ${[1,2],[2,3]}$,这样获得的总美味度为 $5+(-10)+15+(-10)+15 = 15$,花费的总钱数为 $(12^2+22)+(13^2+13)=20$,两者相减为 $-5$;

  14. $Kiana$ 取 $3$ 次寿司,第一次取第 $1$ 个寿司,第二次取第 $2$ 个寿司,第三次取第 $3$ 个寿司,即她取寿司的情况为 ${[1,1],[2,2],[3,3]}$,这样获得的总美味度为 $5+(-10)+15=10$,花费的总钱数为 $(12^2+22)+(13^2+13) = 20$,两者相减为 $-10$。

所以 $Kiana$ 会选择方案 $9$,这时她获得的总美味度减去花费的总钱数的值最大为 $12$。


这个题目就像是一大坨很难拆开的 $shift$
你有 $n$ 个寿司,每个寿司有一个他自己的编号
你可以选若干次,每次可以选择一个区间,当你选择区间 $[l, r]$ 时,你能获得 $\sum_{i = l}^r\sum_{j = i}^r d_{i, j}$
但是每个区间的代价只会被计算一次
然后对于每个编号 如果最后被选择了 $t$ 次
那么你需要付出 $m * id^2 + t * id$ 的代价
没有被选择就不需要付出代价
我们先不考虑付出代价的部分
如果一个区间能被选中多次
直接前缀和搞一搞
现在只能一次
那么我们可以考虑建个图
我们用一个点表示一个区间
点权为那个区间能获得的代价
若区间 $a$ 包含区间 $b$
那就 $a$ 往 $b$ 连一个有向边
这样一来就等价于找这个图的最大权闭合子图 qwq
有一个问题是按照上述建图方式
对于一个长度为 $len$ 的区间会连上 $len * (len - 1) / 2$ 个点
不是很棒
仔细思考一下就会发现我们只需要连长度为 $len - 1$ 的子区间就够了
然后把 $m * id^2 + t * id$ 拆开考虑
$m * id^2$ 表示选中编号为 $id$ 的就要先付出这么大的代价
那么我们先把 $id$ 映射成连续的数字,假如共有 $cnt$ 个
再建 $cnt$ 个点,点权为 $-m * id^2$
所有表示长度为 $1$ 的区间的节点连到往自己那个节点的寿司对应的 $id$ 连边
接下来这个 $t * id$ 就有点头大了
其实仔细思考会发现每个(不是编号)最多只会被选择一次

简单证明一下
如果我们不会出现选择 $[l_1, r_1], [l_2, r_2]$ 且 $l_2 > r_2$ 的情况的
因为这样我们可以直接选择 $[l_1, r_2]$
获利相同,且少支付了 $[l_2, r_1]$ 的代价
证毕

我们把所有表示长度为 $1$ 的区间的节点的权值减去自己那个节点的寿司对应的 $id$
这样还是一个最大权闭合子图模型
就可以解决了


#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

struct Node
{
    int to;
    int w;
    int ne;
};

Node node[N];
int Q[N];   /// 队列  注意数组的大小
int head[N];
int cur[N]; /// 前向弧优化
int di[N];
int ma[N];
int mb[110][110];
int mc[110][110];
int has[N];
int vis[N];
int ss, tt;
int top;
int num;
int n, m;

void Ini()
{
    top = 0;
    memset(head, -1, sizeof(head));
}

void Add_edge(int from, int to, int w)
{
    node[top].to = to;
    node[top].w = w;
    node[top].ne = head[from];
    head[from] = top;
    top ++;
}

bool Build()
{
    int l, r;
    int now;

    memset(di, 0, sizeof(di));
    di[ss] = 1;
    l = r = 0;
    Q[r] = ss;
    r ++;
    while(l != r){
        now = Q[l];
        l ++;
        if(now == tt){
            return true;
        }
        for(int i = head[now]; i != -1; i = node[i].ne){
            int v, w;
    
            v = node[i].to;
            w = node[i].w;
            if(w && !di[v]){
                di[v] = di[now] + 1;
                Q[r] = v;
                r ++;
            }
        }
    }
    
    return false;
}

int Dfs(int u, int maxf)
{
    int ans;
    int qwe;

    if(u == tt){
        return maxf;
    }
    ans = 0;
    for(int &i = cur[u]; i != -1; i = node[i].ne){
        int v, w;
    
        v = node[i].to;
        w = node[i].w;
        if(w && di[v] == di[u] + 1){
            int t;
    
            t = Dfs(v, min(maxf - ans, w));
            node[i].w -= t;
            node[i ^ 1].w += t;
            ans += t;
            if(ans == maxf){
                return ans;
            }
        }
    }
    if(!ans){
        di[u] = -2;
    }
    
    return ans;
}

int Dinic()
{
    int ans;

    ans = 0;
    while(Build()){
        for(int i = 1; i <= tt; i ++){
            cur[i] = head[i];
        }
        ans += Dfs(ss, INF);
    }
    
    return ans;
}

int main(int argc, char const *argv[])
{
    int ans;

    while(scanf("%d%d", &n, &m) == 2){
        Ini();
        memset(has, -1, sizeof(has));
        memset(vis, -1, sizeof(vis));
        num = 1;
        ans = 0;
        for(int i = 1; i <= n; i ++){
            scanf("%d", &ma[i]);
            if(has[ma[i]] == -1){
                has[ma[i]] = num;
                vis[ma[i]] = num;
                // Add_edge(num, tt, ma[i]);
                // Add_edge(tt, num, 0);
                num ++;
            }
        }
        for(int i = 1; i <= n; i ++){
            for(int j = i; j <= n; j ++){
                scanf("%d", &mb[i][j]);
                mc[i][j] = num;
                num ++;
            }
            mb[i][i] -= ma[i];
        }
        num --;
        ss = num + n + 1;
        tt = ss + 1;
        for(int i = 1; i <= n; i ++){
            if(vis[ma[i]] != -1){
                vis[ma[i]] = -1;
                Add_edge(has[ma[i]], tt, ma[i] * ma[i] * m);
                Add_edge(tt, has[ma[i]], 0);
            }
        }
//        cout << num << endl;
//        cout << ss << endl;
        for(int i = 1; i <= n; i ++){
            for(int j = i; j <= n; j ++){
                if(mb[i][j] > 0){
                    ans += mb[i][j];
                    Add_edge(ss, mc[i][j], mb[i][j]);
                    Add_edge(mc[i][j], ss, 0);
                }
                else if(mb[i][j] < 0){
                    Add_edge(mc[i][j], tt, -mb[i][j]);
                    Add_edge(tt, mc[i][j], 0);
                }
                if(i == j){
                    Add_edge(mc[i][j], has[ma[i]], INF);
                    Add_edge(has[ma[i]], mc[i][j], 0);
                }
                else{
                    Add_edge(mc[i][j], mc[i][j - 1], INF);
                    Add_edge(mc[i][j - 1], mc[i][j], 0);
                    Add_edge(mc[i][j], mc[i + 1][j], INF);
                    Add_edge(mc[i + 1][j], mc[i][j], 0);

                }
            }
        }
        printf("%d\n", ans - Dinic());
    }
    
    
    return 0;
}