洛阳400电话洛阳网站seo,手机网站导航特效,客户细分精准营销,网站要求题目描述#xff1a;
P3749 [六省联考 2017] 寿司餐厅
题目描述
Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。
每天晚上#xff0c;这家餐厅都会按顺序提供 n n n 种寿司#xff0c;第 i i i 种寿司有一个代号 a i a_i ai 和美味度 d i , i d_{i, i} di,i
P3749 [六省联考 2017] 寿司餐厅
题目描述
Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。
每天晚上这家餐厅都会按顺序提供 n n n 种寿司第 i i i 种寿司有一个代号 a i a_i ai 和美味度 d i , i d_{i, i} di,i不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的Kiana 也可以无限次取寿司来吃但每种寿司每次只能取一份且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段即 Kiana 可以一次取走第 1 , 2 1, 2 1,2 种寿司各一份也可以一次取走第 2 , 3 2, 3 2,3 种寿司各一份但不可以一次取走第 1 , 3 1, 3 1,3 种寿司。
由于餐厅提供的寿司种类繁多而不同种类的寿司之间相互会有影响三文鱼寿司和鱿鱼寿司一起吃或许会很棒但和水果寿司一起吃就可能会肚子痛。因此Kiana 定义了一个综合美味度 d i , j ( i j ) d_{i, j} \ (i j) di,j (ij)表示在一次取的寿司中如果包含了餐厅提供的从第 i i i 份到第 j j j 份的所有寿司吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时不止一个综合美味度会被累加比如若 Kiana 一次取走了第 1 , 2 , 3 1, 2, 3 1,2,3 种寿司各一份除了 d 1 , 3 d_{1, 3} d1,3 以外 d 1 , 2 , d 2 , 3 d_{1, 2}, d_{2, 3} d1,2,d2,3 也会被累加进总美味度中。
神奇的是Kiana 的美食评判标准是有记忆性的无论是单种寿司的美味度还是多种寿司组合起来的综合美味度在计入 Kiana 的总美味度时都只会被累加一次。比如若 Kiana 某一次取走了第 1 , 2 1, 2 1,2 种寿司各一份另一次取走了第 2 , 3 2, 3 2,3 种寿司各一份那么这两次取寿司的总美味度为 d 1 , 1 d 2 , 2 d 3 , 3 d 1 , 2 d 2 , 3 d_{1, 1} d_{2, 2} d_{3, 3} d_{1, 2} d_{2, 3} d1,1d2,2d3,3d1,2d2,3其中 d 2 , 2 d_{2, 2} d2,2 只会计算一次。
奇怪的是这家寿司餐厅的收费标准很不同寻常。具体来说如果 Kiana 一共吃过了 c ( c 0 ) c \ (c 0) c (c0) 种代号为 x x x 的寿司则她需要为这些寿司付出 m x 2 c x mx^2 cx mx2cx 元钱其中 m m m 是餐厅给出的一个常数。
现在 Kiana 想知道在这家餐厅吃寿司自己能获得的总美味度包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度减去花费的总钱数的最大值是多少。由于她不会算所以希望由你告诉她。
输入格式
第一行包含两个正整数 n , m n, m n,m分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。 第二行包含 n n n 个正整数其中第 k k k 个数 a k a_k ak 表示第 k k k 份寿司的代号。 接下来 n n n 行第 i i i 行包含 n − i 1 n - i 1 n−i1 个整数其中第 j j j 个数 d i , i j − 1 d_{i, ij-1} di,ij−1 表示吃掉寿司能获得的相应的美味度具体含义见问题描述。
输出格式
输出共一行包含一个正整数表示 Kiana 能获得的总美味度减去花费的总钱数的最大值。
输入输出样例 #1
输入 #1
3 1
2 3 2
5 -10 15
-10 15
15输出 #1
12输入输出样例 #2
输入 #2
5 0
1 4 1 3 4
50 99 8 -39 30
68 27 -75 -32
70 24 72
-10 81
-95输出 #2
381输入输出样例 #3
输入 #3
10 1
5 5 4 4 1 2 5 1 5 3
83 91 72 29 22 -5 57 -14 -36 -3
-11 34 45 96 32 73 -1 0 29
-48 68 44 -5 96 66 17 74
88 47 69 -9 2 25 -49
86 -9 -77 62 -10 -30
2 40 95 -74 46
49 -52 2 -51
-55 50 -44
72 22
-68输出 #3
1223说明/提示
样例解释 1
在这组样例中餐厅一共提供了 3 3 3 份寿司它们的代号依次为 a 1 2 , a 2 3 , a 3 2 a_1 2, a_2 3, a_3 2 a12,a23,a32计算价格时的常数 m 1 m 1 m1。
在保证每次取寿司都能获得新的美味度的前提下Kiana 一共有 14 14 14 种不同的吃寿司方案。以下列出其中几种
Kiana 一个寿司也不吃这样她获得的总美味度和花费的总钱数都是 0 0 0两者相减也是 0 0 0Kiana 只取 1 1 1 次寿司且只取第 1 1 1 个寿司即她取寿司的情况为 { [ 1 , 1 ] } \{[1, 1]\} {[1,1]}这样获得的总美味度为 5 5 5花费的总钱数为 1 × 2 2 1 × 2 6 1 \times 2^2 1 \times 2 6 1×221×26两者相减为 − 1 -1 −1Kiana 取 2 2 2 次寿司第一次取第 1 , 2 1, 2 1,2 个寿司第二次取第 2 , 3 2, 3 2,3 个寿司即她取寿司的情况为 { [ 1 , 2 ] , [ 2 , 3 ] } \{[1, 2], [2, 3]\} {[1,2],[2,3]}这样获得的总美味度为 5 ( − 10 ) 15 ( − 10 ) 15 15 5 (-10) 15 (-10) 15 15 5(−10)15(−10)1515花费的总钱数为 ( 1 × 2 2 2 × 2 ) ( 1 × 3 2 1 × 3 ) 20 (1 \times 2^2 2 \times 2) (1 \times 3^2 1 \times 3) 20 (1×222×2)(1×321×3)20两者相减为 − 5 -5 −5Kiana 取 2 2 2 次寿司第一次取第 1 1 1 个寿司第二次取第 3 3 3 个寿司即她取寿司的情况为 { [ 1 , 1 ] , [ 3 , 3 ] } \{[1, 1], [3, 3]\} {[1,1],[3,3]}这样获得的总美味度为 5 15 20 5 15 20 51520花费的总钱数为 1 × 2 2 2 × 2 8 1 \times 2^2 2 \times 2 8 1×222×28两者相减为 12 12 12。
在 14 14 14 种方案中惟一的最优方案是列出的最后一种方案这时她获得的总美味度减去花费的总钱数的值最大为 12 12 12。
数据范围
对于所有数据保证 − 500 ≤ d i , j ≤ 500 -500 \leq d_{i, j} \leq 500 −500≤di,j≤500。
数据的一些特殊约定如下表
Case # n n n a i a_i ai m m m附加限制1 ≤ 2 \leq 2 ≤2 ≤ 30 \leq 30 ≤30 0 0 0-2 ≤ 2 \leq 2 ≤2 ≤ 30 \leq 30 ≤30 1 1 1-3 ≤ 3 \leq 3 ≤3 ≤ 30 \leq 30 ≤30 0 0 0-4 ≤ 3 \leq 3 ≤3 ≤ 30 \leq 30 ≤30 1 1 1-5 ≤ 5 \leq 5 ≤5 ≤ 30 \leq 30 ≤30 0 0 0-6 ≤ 5 \leq 5 ≤5 ≤ 30 \leq 30 ≤30 1 1 1-7 ≤ 10 \leq 10 ≤10 ≤ 30 \leq 30 ≤30 0 0 0所有的 a i a_i ai 相同8 ≤ 10 \leq 10 ≤10 ≤ 30 \leq 30 ≤30 1 1 1-9 ≤ 15 \leq 15 ≤15 ≤ 30 \leq 30 ≤30 0 0 0所有的 a i a_i ai 相同10 ≤ 15 \leq 15 ≤15 ≤ 30 \leq 30 ≤30 1 1 1-11 ≤ 30 \leq 30 ≤30 ≤ 1000 \leq 1000 ≤1000 0 0 0所有的 a i a_i ai 相同12 ≤ 30 \leq 30 ≤30 ≤ 30 \leq 30 ≤30 0 0 0所有的 a i a_i ai 相同13 ≤ 30 \leq 30 ≤30 ≤ 1000 \leq 1000 ≤1000 0 0 0-14 ≤ 30 \leq 30 ≤30 ≤ 1000 \leq 1000 ≤1000 1 1 1-15 ≤ 50 \leq 50 ≤50 ≤ 1000 \leq 1000 ≤1000 0 0 0所有的 a i a_i ai 相同16 ≤ 50 \leq 50 ≤50 ≤ 30 \leq 30 ≤30 0 0 0所有的 a i a_i ai 相同17 ≤ 50 \leq 50 ≤50 ≤ 1000 \leq 1000 ≤1000 0 0 0-18 ≤ 50 \leq 50 ≤50 ≤ 1000 \leq 1000 ≤1000 1 1 1-19 ≤ 100 \leq 100 ≤100 ≤ 1000 \leq 1000 ≤1000 0 0 0-20 ≤ 100 \leq 100 ≤100 ≤ 1000 \leq 1000 ≤1000 1 1 1- 在读题的过程中我们不难发现题目中的几个量之间存在依赖关系且这些依赖关系构成了一张最大权闭合子图再结合题目给的数据范围我们不难想到这道题可以利用网络流去解决。
最大权闭合子图在网络流中是一个常见的模型 有若干个物品每种物品有一个可正可负的价值 v v v 选取了物品就意味着获得了价值。 物品之间有限制关系 x → y x→y x→y 表示若要选择物品 x x x 则必须选择物品 y y y 对于这类问题我们考虑用最小割去解决 我们有源点s汇点t。 源点向每个点都建边每个点都向汇点建边。若割掉源点的边则认为不选当前点若割掉当前点向汇点的连边则认为选择当前点。 那么具体连边要怎么连呢 如果当前点的价值v为正数那么让答案加上当前点的价值并且让当前点和源点连容量为v的边 如果当前点的价值v为负数那么让当前点和汇点连容量为-v的边。 最小割就是在这个最大权闭合子图上的最大流。
那么答案就是 a n s − m a x f l o w ans-maxflow ans−maxflow
好那么回归这个题。 我们将每一个 d i , j d_{i,j} di,j都看做一个点价值就是他本身的值。 且这些点根点之间都有依赖关系若想选 d i , j d_{i,j} di,j就必须选 d i , j − 1 d_{i,j-1} di,j−1和 d i 1 , j d_{i1,j} di1,j 只需要让当前点向这两个点连容量为正无穷的边即可。 同时这个题还有一个寿司种类的限制想要处理这个限制最好的办法就是把寿司种类也加入这个图中且他的价值为 − m ∗ a [ i ] ∗ a [ i ] -m*a[i]*a[i] −m∗a[i]∗a[i] 他跟 d i , i d_{i,i} di,i存在限制 d i , i − a [ i ] d_{i,i}-a[i] di,i−a[i] 且我们没选一个寿司就要扣除他种类编号的价值也就是令 d i , i d_{i,i} di,i的价值再减去 a [ i ] a[i] a[i] 在这张图上跑最大流即可求出答案。 #includebits/stdc.h
using namespace std;const int N 1e4100,inf 1e9100;
struct Node{int y,Next,v;
}e[100*N];
int len 1,Linkk[N];
int n,m;
int a[N],d[1000][1000];
int id[1000][1000],idx[10*N];
int ans 0,cnt 0;
int st,ed;
map int , int M;void Insert(int x,int y,int v){e[len] (Node){y,Linkk[x],v};Linkk[x] len;e[len] (Node){x,Linkk[y],0};Linkk[y] len;
}int de[N];bool bfs(){queue int q;for (int i 1; i n; i) de[i] 0;de[st] 1; q.push(st);while (q.size()){int x q.front(); q.pop();for (int i Linkk[x]; i; i e[i].Next){int y e[i].y;if (de[y] || e[i].v 0) continue;de[y] de[x]1;if (y ed) return 1;q.push(y);}}return 0;
}int dinic(int x,int re){if (x ed) return re;int now re;for (int i Linkk[x]; i re; i e[i].Next){int y e[i].y;if (e[i].v 0 || de[y] ! de[x]1) continue;int k dinic(y,min(e[i].v,re));if (k 0) de[y] 0;re-k;e[i].v-k; e[i^1].vk;}return now-re;
}void Work(){len 1;cinnm;st cnt; ed cnt;for (int i 1; i n; i){cina[i];if (!M[a[i]]) M[a[i]] 1 , idx[a[i]] cnt;}M.clear();for (int i 1; i n; i){if (M[a[i]]) continue;M[a[i]] 1;if (m) Insert(idx[a[i]],ed,m*a[i]*a[i]);}for (int i 1; i n; i)for (int j i; j n; j){cind[i][j],id[i][j] cnt;int v d[i][j];if (i j){v v-a[i];if (m) Insert(id[i][j],idx[a[i]],inf);}if (v 0){ansv;Insert(st,id[i][j],v);}else Insert(id[i][j],ed,-v);}for (int i 1; i n; i)for (int j i1; j n; j){int x id[i][j] ,y ;if (i 1 n) y id[i1][j],Insert(x,y,inf);y id[i][j-1]; Insert(x,y,inf);}int maxf 0;n cnt;while (bfs()) maxfdinic(st,inf);coutans-maxfendl;return;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int _ 1; while (_--) Work();return 0;
}
