原文地址：http://www.cnblogs.com/GXZlegend/p/6795784.html
题目描述
Kiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上，这家餐厅都会按顺序提供n种寿司，第i种寿司有一个代号ai和美味度di,i，不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的，Kiana也可以无限次取寿司来吃，但每种寿司每次只能取一份，且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段，即Kiana可以一次取走第1,2种寿司各一份，也可以一次取走第2,3种寿司各一份，但不可以一次取走第1,3种寿司。由于餐厅提供的寿司种类繁多，而不同种类的寿司之间相互会有影响：三文鱼寿司和鱿鱼寿司一起吃或许会很棒，但和水果寿司一起吃就可能会肚子痛。因此，Kiana定义了一个综合美味度di,j(i<j)，表示在一次取的寿司中，如果包含了餐厅提供的从第i份到第j份的所有寿司，吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间，所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时，不止一个综合美味度会被累加，比如若Kiana一次取走了第1,2,3种寿司各一份，除了d1,3以外，d1,2,d2,3也会被累加进总美味度中。神奇的是，Kiana的美食评判标准是有记忆性的，无论是单种寿司的美味度，还是多种寿司组合起来的综合美味度，在计入Kiana的总美味度时都只会被累加一次。比如，若Kiana某一次取走了第1,2种寿司各一份，另一次取走了第2,3种寿司各一份，那么这两次取寿司的总美味度为d1,1+d2,2+d3,3+d1,2+d2,3，其中d2,2只会计算一次。奇怪的是，这家寿司餐厅的收费标准很不同寻常。具体来说，如果Kiana一共吃过了c(c>0)种代号为x的寿司，则她需要为这些寿司付出mx^2+cx元钱，其中m是餐厅给出的一个常数。现在Kiana想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她不会算，所以希望由你告诉她
输入
输出
输出共一行包含一个正整数，表示Kiana能获得的总美味度减去花费的总钱数的最大值。
样例输入
3 1 2 3 2 5 -10 15 -10 15 15
样例输出
12
题解
网络流最大权闭合图（竟然忘了。。。）
对于出题人的数据，我们可以换个姿势来看：
5 -10 15
-10 15
15
可以看出每次选择都是一个直角三角形。
那么对于每个点(i,j) (j>i)，如果它被选择，那么点(i,j-1)和点(i+1,j)也一定被选择，以此类推。
根据这个来建一个点权图。
对于点(i,j) (j>i)，点权为d[i][j]，并向点(i,j-1)和点(i+1,j)连边。
对于点(i,i)，点权为d[i][i]-a[i]，即收益减去费用，并向编号a[i]连边。
对于编号p，点权为-m*p*p。
所求为最大权闭合图，所以转化为网络流最小割来求。
具体建图方法不用像上面说的先建点权图，直接建立网络图即可。
代码真心不长。
#include#include #include #define inf 0x3f3f3f3fusing namespace std;queue q;int a[10010] , v[110][110] , id[110][110] , tot , head[10010] , to[100010] , val[100010] , next[100010] , cnt = 1 , s , t , dis[10010];void add(int x , int y , int z){ to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){ int x , i; memset(dis , 0 , sizeof(dis)); while(!q.empty()) q.pop(); dis[s] = 1 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) { if(val[i] && !dis[to[i]]) { dis[to[i]] = dis[x] + 1; if(to[i] == t) return 1; q.push(to[i]); } } } return 0;}int dinic(int x , int low){ if(x == t) return low; int temp = low , i , k; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] == dis[x] + 1) { k = dinic(to[i] , min(temp , val[i])); if(!k) dis[to[i]] = 0; val[i] -= k , val[i ^ 1] += k; if(!(temp -= k)) break; } } return low - temp;}int main(){ int n , m , k = 0 , i , j , sum = 0; scanf("%d%d" , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , k = max(k , a[i]); for(i = 1 ; i <= n ; i ++ ) for(j = i ; j <= n ; j ++ ) scanf("%d" , &v[i][j]) , id[i][j] = ++tot; s = 0 , t = tot + k + 1; for(i = 1 ; i <= k ; i ++ ) add(tot + i , t , m * i * i); for(i = 1 ; i <= n ; i ++ ) add(id[i][i] , tot + a[i] , inf) , v[i][i] -= a[i]; for(i = 1 ; i <= n ; i ++ ) { for(j = i ; j <= n ; j ++ ) { if(v[i][j] > 0) add(s , id[i][j] , v[i][j]) , sum += v[i][j]; if(v[i][j] < 0) add(id[i][j] , t , -v[i][j]); if(j > i) add(id[i][j] , id[i][j - 1] , inf) , add(id[i][j] , id[i + 1][j] , inf); } } while(bfs()) sum -= dinic(s , inf); printf("%d\n" , sum); return 0;}