列表

详情

NC20438. [SHOI2017]寿司餐厅

描述

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想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她不会算，所以希望由你告诉她

输入描述

第一行包含两个正整数n,m，分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。 
第二行包含n个正整数，其中第k个数ak表示第k份寿司的代号。 
接下来n行，第i行包含n-i+1个整数，其中第j个数di,i+j-1表示吃掉寿司能获得的相应的美味度，具体含义见问题描述。 
N ≤ 100,Ai ≤ 1000

输出描述

输出共一行包含一个正整数，表示Kiana能获得的总美味度减去花费的总钱数的最大值。

示例1

输入: 

3 1
2 3 2
5 -10 15
-10 15
15

输出: 

12

说明:

【样例1说明】
在这组样例中，餐厅一共提供了3份寿司，它们的代号依次为a1=2，a2=3，a3=2，计算价格时的常数m=1。在保证每
次取寿司都能获得新的美味度的前提下，Kiana一共有14种不同的吃寿司方案：
1.Kiana一个寿司也不吃，这样她获得的总美味度和花费的总钱数都是0，两者相减也是0；
2.Kiana只取1次寿司，且只取第1个寿司，即她取寿司的情况为{[1,1]}，这样获得的总美味度为5，花费的总钱数
为1-2^2+1*2=6，两者相减为-1；
3.Kiana只取1次寿司，且只取第2个寿司，即她取寿司的情况为{[2,2]}，这样获得的总美味度为-10，花费的总钱
数为1-3^2+1*3=12，两者相减为-22；
4.Kiana只取1次寿司，且只取第3个寿司，即她取寿司的情况为{[3,3]}，这样获得的总美味度为15，花费的总钱数
为1*2^2+1*2=6，两者相减为9；
5.Kiana只取1次寿司，且取第1,2个寿司，即她取寿司的情况为{[1,2]}，这样获得的总美味度为5+(-10)+(-10)=-1
5，花费的总钱数为(1-2^2+1*2)+(1-3^2+1*3)=18，两者相减为-33；
6.Kiana只取1次寿司，且取第2,3个寿司，即她取寿司的情况为{[2,3]}，这样获得的总美味度为(-10)+15+15=20，
花费的总钱数为(1-2^2+1*2)+(1*3^2+1*3)=18，两者相减为2；
7.Kiana只取1次寿司，且取第1,2,3个寿司，即她取寿司的情况为{[1,3]}，这样获得的总美味度为5+(-10)+15+(-1
0)+15+15=30，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为10。
8.Kiana取2次寿司，第一次取第1个寿司，第二次取第2个寿司，即她取寿司的情况为{[1,1],[2,2]}，这样获得的
总美味度为5+(-10)=-5，花费的总钱数为(1*2^2+1*2)+(1*3^2+1*3)=18，两者相减为-23；
9.Kiana取2次寿司，第一次取第1个寿司，第二次取第3个寿司，即她取寿司的情况为{[1,1],[3,3]}，这样获得的
总美味度为5+15=20，花费的总钱数为1*2^2+2*2=8，两者相减为12；
10.Kiana取2次寿司，第一次取第2个寿司，第二次取第3个寿司，即她取寿司的情况为{[2,2],[3,3]}，这样获得的
总美味度为(-10)+15=5，花费的总钱数为(1*2^2+1*2)+(1*3^2+1*3)=18，两者相减为-13；
11.Kiana取2次寿司，第一次取第1,2个寿司，第二次取第3个寿司，即她取寿司的情况为{[1,2],[3,3]}，这样获得
的总美味度为5+(-10)+(-10)+15=0，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为-20；
12.Kiana取2次寿司，第一次取第1个寿司，第二次取第2,3个寿司，即她取寿司的情况为{[1,1],[2,3]}，这样获得
的总美味度为5+(-10)+15+15=25，花费的总钱数为(1-22+2-2)+(1-32+1-3)=20，两者相减为5；
13.Kiana取2次寿司，第一次取第1,2个寿司，第二次取第2,3个寿司，即她取寿司的情况为{[1,2],[2,3]}，这样获
得的总美味度为5+(-10)+15+(-10)+15=15，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为-5；
14.Kiana取3次寿司，第一次取第1个寿司，第二次取第2个寿司，第三次取第3个寿司，即她取寿司的情况为{[1,1]
,[2,2],[3,3]}，这样获得的总美味度为5+(-10)+15=10，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减
为-10。
所以Kiana会选择方案9，这时她获得的总美味度减去花费的总钱数的值最大为12。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 100ms, 内存消耗: 996K, 提交时间: 2019-07-19 10:34:27 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2 + 5, INF = 0x3f3f3f3f, M = N * N * 2;
#define ri register int
// #define endl '\n'

struct edge {
  int v, w;
} G[M * 10];
int head[N * N + 2 * N], nxt[M * 10], n, m, tot = 1, S, T;
int x[N];
void add(int u, int v, int w) {
  G[++tot] = {v, w}, nxt[tot] = head[u], head[u] = tot;
  G[++tot] = {u, 0}, nxt[tot] = head[v], head[v] = tot;
}

int L[N * N + 2 * N], cur[N * N + 2 * N];
bool bfs() {
  memset(L, 0, sizeof L);
  memcpy(cur, head, sizeof head);
  queue<int> q;
  q.push(S), L[S] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = nxt[i]) {
      int v = G[i].v, w = G[i].w;
      if (!L[v] && w) L[v] = L[u] + 1, q.push(v);
    }
  }
  return L[T];
}

int dfs(int u, int f) {
  if (u == T) return f;
  int flow = 0;
  for (int &i = cur[u]; i && f > flow; i = nxt[i]) {
    int v = G[i].v, w = G[i].w;
    if (L[v] != L[u] + 1 || !w) continue;
    int d = dfs(v, min(f - flow, w));
    if (!d) continue;
    flow += d, G[i].w -= d, G[i ^ 1].w += d;
  }
  return flow;
}

int maxflow() {
  int ans = 0;
  while (bfs()) ans += dfs(S, INF);
  return ans;
}

map<int, int> vis;
int a[N][N], id[N][N];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  T = n * n + n * 2 + 2;
  int sum = 0, cnt = n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
    if (!vis[x[i]]) vis[x[i]] = ++cnt, add(cnt, T, x[i] * x[i] * m);
    add(i, vis[x[i]], INF), add(i, T, x[i]);
  }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) id[i][j] = (i == j) ? i : ++cnt;
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] >= 0)
        add(S, id[i][j], a[i][j]), sum += a[i][j];
      else
        add(id[i][j], T, -a[i][j]);
      if (i != j) add(id[i][j], id[i + 1][j], INF), add(id[i][j], id[i][j - 1], INF);
    }
  cout << sum - maxflow() << endl;
}

上一题

© 2024 nowcoder.com