Codeforces - 434D

題目大意:

給定一個長為n的序列，序列中的第i為上的值\(x_i\),序列第i位上的值\(x_i\in[l_i,r_i]\),價值為\(f_i(x_i)\),其中\(f_i(x) = a_ix^2 + b_ix + c_i\),同時給出m個限制條件,每個限制條件用一個三元組\(<u,v,d>\)來表示,需要序列滿足\(x_u \leq x_v + d\)。求在滿足所限制條件的情況下的\(f_i(x_i)\)的最大和。
其中滿足(\(1 \leq n \leq 50, 0 \leq m \leq 100 , -100 \leq l_i \leq r_i \leq 100)\)

題目解答：

這道題跟[bzoj 3144 切糕]類似,由于網上關于切糕的題解已經爛大街了，在這里就不說了.
首先我們考慮在沒有\(x_i\)的限制之下的答案計算：
直接取每段內的\(max\)不就好了嘛... ...

開一開腦洞，你就會構造出一個跟切糕差不多的層次模型

這不過這次是"最大割"而已

我們可以把所有有價值的邊權全部都被所有值中的最大值減一下

這樣我們直接求最小流再調整就行了。

而對于\(X_u <= X_v + d\)的限制

我們直接應用和切糕一樣的思想來限制就可以了

一遍最大流即可

\(ans = (max(f_i(x)) + 1)*n - maxflow\)

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; inline void read(int &x){x=0;char ch;bool flag = false;while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x; } inline int cat_max(const int &a,const int &b){return a>b ? a:b;} inline int cat_min(const int &a,const int &b){return a<b ? a:b;} const int maxn = 51; const int maxm = 128; const int maxnode = 25400; const int maxedge = 254000; const int inf = 0x3f3f3f3f; struct Edge{int to,next,cap; }G[maxedge]; int head[maxnode],cnt=1; void add(int u,int v,int c){G[++cnt].to = v;G[cnt].next = head[u];G[cnt].cap = c;head[u] = cnt; } inline void insert(int u,int v,int c){add(u,v,c);add(v,u,0); } int dis[maxnode],q[maxnode],l,r; int S,T; #define v G[i].to bool bfs(){memset(dis,-1,sizeof dis);dis[S] = 0;l = 0;r = -1;q[++r] = S;while(l <= r){int u = q[l++];for(int i = head[u];i;i=G[i].next){if(dis[v] == -1 && G[i].cap){dis[v] = dis[u] + 1;q[++r] = v;}}}return dis[T] != -1; }int cur[maxnode]; int dfs(int u,int f){if(u == T || f == 0) return f;int ret = 0;for(int &i = cur[u];i;i=G[i].next){if(dis[v] == dis[u] + 1 && G[i].cap){int x = dfs(v,cat_min(G[i].cap,f));ret += x;f -= x;G[i].cap -= x;G[i^1].cap += x;if(f == 0) break;}}if(ret == 0) dis[u] = -1;return ret; } inline int dinic(){int ret = 0;while(bfs()){memcpy(cur,head,sizeof head);ret += dfs(S,inf);}return ret; } #undef v int n; inline int f(int x,int y){y += 102;return x*210+y; } int a[maxn],b[maxn],c[maxn],le[maxn],ri[maxn]; inline int calc(int i,int x){return a[i]*x*x+b[i]*x+c[i]; } int main(){S = maxnode - 5;T = S+1;read(n);int m;read(m);int lim = -inf;for(int i=1;i<=n;++i){read(a[i]);read(b[i]);read(c[i]);}for(int i=1;i<=n;++i){read(le[i]);read(ri[i]);insert(S,f(i,le[i]-1),inf);for(int j=le[i];j<=ri[i];++j){lim = cat_max(lim,calc(i,j)+1); }insert(f(i,ri[i]),T,inf);}for(int i=1;i<=n;++i){for(int j=le[i];j<=ri[i];++j){insert(f(i,j-1),f(i,j),lim - calc(i,j));}}for(int i=1,u,v,d;i<=m;++i){read(u);read(v);read(d);for(int j=le[u];j<=ri[u];++j){if(j - d - 1 >= le[v] - 1 && j - d -1 <= ri[v])insert(f(u,j-1),f(v,j-d-1),inf);}}int ans = dinic();printf("%d\n",lim*n - ans);getchar();getchar();return 0; }

轉載于:https://www.cnblogs.com/Skyminer/p/6337959.html

總結

以上是生活随笔為你收集整理的CodeForces - 434D Nanami's Power Plant的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。