设第i天是否去逛街为a[i]，c[i]表示第i天的智商，a[i]=1表示去逛街，a[i]=0表示不去
则可得2n个不等式
a[1]+a[2]+...+a[n]<=k
a[2]+a[3]+...+a[n+1]<=k
...
a[2n+1]+....+a[3n]<=k
求c[1]*a[1]+c[2]*a[2]+...+c[3n]*a[3n]的最大值
添加一个辅助变量
a[1]+a[2]+...+a[n]+y[1]=k
a[2]+a[3]+...+a[n+1]+y[2]=k
...
a[2n+1]+....+a[3n]+y[2n+1]=k
0<=y[i]<=k
将上述不等式相邻两个相减
y[1]+a[1]=a[n+1]+y[2]。。。。。。。。。1
y[2]+a[2]=a[n+2]+y[3]。。。。。。。。。2
......
y[n+1]+a[n+1]=a[2n+1]+y[n+2]。。。。。。。n+1
......
y[2n]+a[2n]=a[3n]+y[2n+1]。。。。。。。。2n
根据网络中每个节点流入量等于流出量的性质
将上述等式编号并抽象成网络中的点，变量a[i]和y[i]抽象为网络中的有向边（弧）
问题等价于求最大费用最大流
以a[n+1]为例 可以看成是节点1部分流出量和节点n+1的部分流入量于是可以建边从n+1到1
故根据这些等式可以建图
设源点为0，汇点为2n+3
i到n+i连一条弧，流量上限为1，费用为c[n+i] 1<=i<=n
i到i+1连一条弧，流量上限为k，费用为0（即为辅助变量y）1<=i<=2n-1
这时发现题目的k还没用上，
于是发现上述等式成立必需满足这两个等式
a[1]+a[2]+...+a[n]+y[1]=k。。。。。2n+1
a[2n+1]+....+a[3n]+y[2n+1]=k。。。。。2n+2
于是建一个节点2n+1
为了满足2n+1式
则由源点向节点2n+1连一条流量上限为k的边，费用为0。
由节点2n+1向i连一条流量上限为1的边，费用为c[i](即为变量a[i]）1<=i<=n
由2n+1向1连一条流量上限为k的边，费用为0(即y[1])
同理建一个节点2n+2
为了满足2n+2式则由节点2n+2向汇点连一条流量上限为k的边，费用为0。
由节点i向2n+2连一条流量上限为1的边，费用为ci
建图完毕，剩下就是套算法。

我有个不用线性规划的做法，简单费用流。

类似于网络流24题中的最长k可重区间集问题，将每个点拆成i和i'，S向SS连容量为k费用为0的边，SS向每个点i连容量为1费用为0的边，每个i向i'连容量为1费用为价值的边，每个i'向T连容量为1费用为0的边，i'向[i+n,i+n*3]中的所有点连容量为1费用为0的边，跑最大费用流。

代码

#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <vector>

typedef long long ll;
const int N = 1205;
const ll INF = 1e18;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

ll min(ll x, ll y) {
    if (x <= y) return x; return y;
}

struct Edge {
    int from, to; ll flow, cap, cost;
};
std::vector<Edge> edges;
std::vector<int> G[N];
int S, SS, T, n, p[N]; ll d[N], a[N];

void addedge(int from, int to, ll cap, ll cost) {
    edges.push_back((Edge){from, to, 0, cap, cost});
    edges.push_back((Edge){to, from, 0, 0, -cost});
    int size = edges.size();
    G[from].push_back(size - 2);
    G[to].push_back(size - 1);
}

bool SPFA(ll &flow, ll &cost) {
    bool inq[N] = {}; inq[S] = 1;
    std::queue<int> Q; Q.push(S);
    for (int i = 0; i < n; ++ i) d[i] = INF;
    d[S] = p[S] = 0, a[S] = INF;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(), inq[u] = 0;
        int size = G[u].size();
         for (int i = 0; i < size; ++ i) {
            Edge e = edges[G[u][i]];
            if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                p[e.to] = G[u][i];
                a[e.to] = min(a[u], e.cap - e.flow);
                if (!inq[e.to]) Q.push(e.to), inq[e.to] = 1;
            }
        }
    }
    if (d[T] == INF) return false;
    flow += a[T], cost += a[T] * d[T];
    int x = T;
    while (x != S) {
        edges[p[x]].flow += a[T], edges[p[x]^1].flow -= a[T];
        x = edges[p[x]].from;
    }
    return true;
}

ll mincost() {
    ll flow = 0, cost = 0;
    while (SPFA(flow, cost)) {}
    return cost;
}

int main() {
    n = read(); int k = read(); S = 0, SS = n * 6 + 1, T = SS + 1;
    addedge(S, SS, k, 0);
    for (int i = 1; i <= n * 3; ++ i) {
        int x = read();
        addedge(SS, i, 1, 0);
        addedge(i, i + n * 3, 1, -x);
        addedge(i + n * 3, T, 1, 0);
        for (int j = i + n; j <= n * 3; ++ j)
            addedge(i + n * 3, j, 1, 0);
    }
    n = T + 1;
    printf("%lld\n", -mincost());
    return 0;
}

这一题用线性规划可破。

直接网络流

我提前发题解了