【题解】[HNOI2013] 数列 Luogu P3228 —— by Peipei

上面是我的 logo 叽哩嘎啦哈哈哈哈
蒟蒻的 Q 啦：1208247864 owo dalao 们来加啦

这个题啊，真像个费用流
然而呢 费用流也能跑
就是可能不 AK (我没试，不知道啊)
然后呢，我们考虑正解

首先我们知道我们要把所有的点放给两侧，使之最后 ans 最小
那么，我们又发现 m 是如此的小，那我们枚举好了

我们既然要求两边都小，那我们先确定一边好了
然后，我们记录所有 m 个煤矿的一个变量 del

del[i] = c[i][0]-c[i][to];
to 是现在枚举的另一个新工厂

然后根据 del[i] 把所有的煤矿排序，在前面取够 b 个
剩下的全给另一个 to
最后加上两个工厂的 h
更新 ans 就好了

#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 100100
using namespace std;

IL void of(R II &a) {
    R char c=getchar (); R II w=1, p=0;
    while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar (); }
    while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar (); }
    a=w*p;
}

/* -------------------- Peipei -------------------- */

II m,b,n,ans=1e9,WEI;
II H[I];

struct owo {
    II a,del; II c[55];
    friend bool operator < (owo a1,owo a2) {
        return a1.del<a2.del;
    }
} D[I];

int main()
{
    of(m); of(b); of(H[0]); of(n);
    for(R II i=1;i<=m;i++) of(D[i].a);
    for(R II j=1;j<=n;j++) of(H[j]);
    for(R II j=0;j<=n;j++)
    for(R II i=1;i<=m;i++) of(D[i].c[j]);

    for(R II i=1;i<=n;i++)
    {
        R II wei=1, all=b, W=0, now;
        for(R II j=1;j<=m;j++) 
            D[j].del=D[j].c[0]-D[j].c[i];
        sort(D+1,D+m+1);

        while (all) {
            now=min(all,D[wei].a);
            all-=now;
            W+=(D[wei].del+D[wei].c[i])*now;
            if(D[wei].a==now) wei++, now=0;
        }

        while (wei<=m) {
            W+=D[wei].c[i]*(D[wei].a-now);
            now=0; wei++;
        }

        if(ans>W+H[i]+H[0]) WEI=i;
        ans=min(ans,W+H[i]+H[0]);
    }

    printf("%d\n%d\n",WEI,ans);
    exit(0);
}