题解

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) E

很容易将题目转化成一个网络流的模型，$S$向每个点连$p _ i$的边，每个点又向$T$连$s _ i$的边，然后对于任意$i < j$，连$c$的边，然后求最大流，也就是最小割，边数是$O(n^2)$的，网络流会TLE。
考虑怎么求最小割（ST割），设$f[i][j]$表示前$i$个点，有$j$个点在S割中的最小割值。
根据$i$是否在S割中分类，那么有：

$$f[i][j] = \min\{ f[i - 1][j - 1] + s _ i, f[i - 1][j] + p _ i + j\cdot c \}$$
很显然最小值一定是合法的而且就是最小割。