1.k取方格数
一个矩阵格子，从最左上角出发到最右下角，走k次，每个格子上有一个数，走过一次就变为0，问能取到的所有数字之和最大值。
每个点 i 拆成两个点 i 和 i'（左半边与右半边），两点之间连两条边一条容量为 1，费用为 -a[i]， 另一条容量为无穷，费用为0
每个点的右半边与相邻点的左半边连起来，容量为无穷（应该是只要比k大就行），费用为0。
从源点到左上角的点连一条边，容量为 k， 费用为0，从右下角到汇点连一条边，容量为k，费用为0，跑一次最小费用最大流
2.小改
此时费用变为，该边上流量的平方，比如一条边容量为10，流量为2，则费用为4
思路：原本的算法只对费用与流量成正比的时候有效，现在变成一个凸函数，不能直接使用，则拆边，把一条容量为n的边拆成n条，分别为
容量为1，费用为 1^2 - 0^2
容量为2，费用为 2^2 - 1^2
......
容量为n， 费用为 n^2 - (n-1)^2
3.序列选数
给一个长为 n 的序列，从中分别取出1,2,3，...，n/2个不相邻的数，分别和最大，输出
当 只取一个数的时候，很明显答案就是序列中最大的那个数
使用费用流的思路，当我们要取第二个及以后的数的时候，需要允许反悔，则对
i - 1, i, i + 1，三个数，如果我们取了第 i 个数，那么i-1和i+1就不能取，除非反悔，发现 a[i-1]+a[i+1] >= a[i]
那么只需要在取了第i个点后，将这三个点合并成为一个值为 a[i-1]+a[i+1]-a[i]的新点即可
折叠
#include<bits/stdc++.h>
using namespace std;
const int MXN = 100010, inf = 0x3f3f3f3f;
struct Range{
int l, pre, nxt, v;
bool operator<(Range x)const{ return v < x.v;}
}r[MXN];
priority_queue<Range> q;
int main(){
int t, n, ans, cnt;
scanf("%d", &t);
while(t--){
ans = 0;
while(!q.empty()) q.pop();
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d", &r[i].v);
r[i].pre = i-1, r[i].nxt = i+1; // 前驱后继
q.push((Range){i, 0, 0, r[i].v});
}
cnt = n/2;
while(!q.empty() && cnt){
Range k = q.top();
q.pop();
Range &y = r[k.l];
if(y.v != k.v) continue; // 被合并的点，此时就不能再选了
ans += y.v, cnt--;
printf("%d\n", ans);
Range &x = r[y.pre], &z = r[y.nxt];
if(y.pre < 1 && y.nxt > n) continue; // 不符合规定的点
else if(y.pre == 0) y.v = z.v = -inf, r[z.nxt].pre = 0; //如果这个点没有前驱或者后继，直接删点
//没有反悔的可能
else if(y.nxt > n) x.v = y.v = -inf, r[x.pre].nxt = y.nxt;
else{
x.v += z.v - y.v, x.nxt = z.nxt;
y.v = z.v = -inf;
r[z.nxt].pre = y.pre;
k.v = x.v, k.l = y.pre;
q.push(k);
}
// 否则对于三个点， 保留最左边的点，旁边两点删去
}
}
return 0;
}