【题目】

【题意】给定n种寿司的代号，取区间[i,j]的寿司收益是d[i,j]和所有子区间的d，吃了c（c>0）种代号x的寿司的代价是mx^2+cx，给定n,m和矩阵d（有负数！），求最大收益。n<=100。

【算法】最大权闭合子图

【题解】开始考虑每个区间建一个收益点向区间内的寿司连边，然后对每个代号新建一个点权为-mx^2的点，每种寿司寿司连向代号点，这样就是求最大权闭合子图了。

但是这样边数是n^3，可能过不了。

考虑优化，区间$[i,j]$只需要连向$[i,j-1]$和$[i+1,j]$就可以了，所有区间$[i,i]$的点权为d[i,i]-a[i]，这样边数只有n^2，复杂度O(n^4)。

#include
      
       #include
       
        #include
        
         using namespace std;const int inf=0x3f3f3f3f;int n,m,S,T,a[110];namespace nwf{    const int maxn=20010,maxm=40010;    int tot=1,first[maxn],d[maxn],q[maxn],cur[maxn];    struct edge{
    int v,f,from;}e[maxm*2];    void insert(int u,int v,int f){        tot++;e[tot].v=v;e[tot].f=f;e[tot].from=first[u];first[u]=tot;        tot++;e[tot].v=u;e[tot].f=0;e[tot].from=first[v];first[v]=tot;    }    bool bfs(){        memset(d,-1,sizeof(d));        d[S]=0;        int head=0,tail=1;q[head]=S;        while(head
         
          0)nwf::insert(S,(i-1)*n+j,u),ans+=u;else nwf::insert((i-1)*n+j,T,-u);//            }            else if(u-a[i]>0)nwf::insert(S,(i-1)*n+j,u-a[i]),ans+=u-a[i];else nwf::insert((i-1)*n+j,T,a[i]-u);        }    }    for(int i=1;i<=1000;i++){        nwf::insert(n*n+i,T,i*i*m);        for(int j=1;j<=n;j++)if(a[j]==i)nwf::insert((j-1)*n+j,n*n+i,inf);    }    printf("%d",ans-nwf::dinic());    return 0;}