转移顺序的艺术 luogu4394 + lougu2966 + luogu3537

lougu4394:

N个政党要组成一个联合内阁，每个党都有自己的席位数.

现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.

对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.

将最后一个限制转化成，去掉所选的最小的，剩下的小于等于总数的一半

根据上面的转化，将a[i],从大到小排序考虑，01背包即可

code:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int MAXX = 330;

int sum, n;

int a[MAXX];

bool f[310][100100];

inline bool cmp (int a, int b) {

  return a > b;

}

int main() {

  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) {

    scanf("%d", &a[i]);

    sum += a[i];

  }

  sort(a + 1, a + n + 1, cmp);

  f[0][0] = 1;

  for (int i = 1; i <= n; ++i) {

    for (int j = 0; j <= sum; ++j) {

      f[i][j] |= f[i - 1][j];

      if(j - a[i] >= 0 && j - a[i] <= (sum / 2))f[i][j] |= f[i - 1][j - a[i]];

    }

  }

  int ans = 0;

  for (int i = sum / 2; i <= sum ; ++i) if (f[n][i]) ans = i;

  printf("%d", ans);

  return 0;

}

luogu2966:

在无向连通图中，有点权，有边权，给出多次询问起点和终点的（路径边权和 + 路径上最大值）的最小值

根据floyd，f[k][i][j]表示从i到j,经过的编号<=k,的最短路，其实k的顺序没有关系，我们不妨按照点权从小打到大排序抉择，当前的k一定是路径上的最大点（不包括i,j）

code:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cctype>

using namespace std;

const int MAXX = 300;

struct node

{

  int id, val;

  bool operator < (const node & a) const {

    return val < a.val;

  }

}pot[MAXX];

int dis[MAXX][MAXX], ans[MAXX][MAXX], mp[MAXX][MAXX], pm[MAXX];

int n, m, q;

inline int rd() {

  int x = 0; bool f = 0;

  char c = getchar();

  while (!isdigit(c)) {

    if (c == '-') f = 1;

    c =getchar();

  }

  while (isdigit(c)) {

    x = (x << 1) + (x << 3) + (c ^ 48);

    c = getchar();

  }

  return f ? -x : x;

}

int main() {

  n = rd(); m = rd(); q = rd();

  memset(dis, 0x3f, sizeof(dis));

  memset(ans, 0x3f, sizeof(ans));

  memset(mp, 0x3f, sizeof(mp));

  for (int i = 1; i <= n; ++i) {

    dis[i][i] = 0x3f3f3f3f;

    pot[i].id = i;

    pot[i].val = rd();

    pm[i] = pot[i].val;

  }

  sort(pot + 1, pot + 1 + n);

  for (int i = 1; i <= m; ++i) {

    int x, y, z;

    x = rd(); y = rd(); z = rd();

    mp[x][y] = mp[y][x] = min(min(mp[x][y], mp[y][x]), z);

    dis[x][y] = dis[y][x] = min(dis[x][y], min(dis[y][x], mp[x][y]));

  }

  for (int k = 1; k <= n; ++k) {

    for (int i = 1; i <= n; ++i) {

      for (int j = 1; j <= n; ++j) {

        dis[i][j] = min (dis[i][j], dis[i][pot[k].id] + dis[pot[k].id][j]);

        ans[i][j] = min (ans[i][j], dis[i][j] + max(max( pm[i], pm[j] ), pot[k].val) );

      }

    }

  }

  while (q--) {

    int u, v;

    u = rd(); v =rd();

    printf("%d\n",min(ans[u][v], ans[v][u]));

  }

  return 0;

}

lougu 3537:

有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。

再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得：

对于每个选的物品i，满足a[i]<=m且b[i]>m+s。

所有选出物品的c[i]的和正好是k。

如果没有限制的话那么直接背包可行性dp即可

如果只有a[i] <= m，那我们可以离线，将询问按照m从小到大排序，将物品按照a从小到大排序，对于一个询问我们处理比他小的a，对于a我们处理刚好比他大的m，这样这个限制就解决了

我们考虑最后一个限制，不如dp一下，这条限制相当于所选的集合中最小的b要大于\(m + s\)，那我们设计状态为f[k]，表示恰好装k的方案中最小的b最大是多少，最后我们只要是判断一下\(f[k] > m + s\),即可

code:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cctype>

#include <algorithm>

using namespace std;

const int MAXX = 1010;

struct node

{

  int a, b, c;

  bool operator < (const node & A) const {

    return a < A.a;

  }

}t[MAXX];

struct query

{

  int m, k, s, id;

  bool operator < (const query & A) const {

    return m < A.m;

  }

}q[MAXX * MAXX];

int n, k;

int f[100100];

bool ans[1001000];

int main() {

  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) scanf("%d%d%d", &t[i].c, &t[i].a, &t[i].b);

  scanf("%d", &k);

  for (int i = 1; i <= k; ++i) {

    scanf("%d%d%d",&q[i].m, &q[i].k, &q[i].s);

    q[i].id = i;

  }

  sort(t + 1, t + n + 1);

  sort(q + 1, q + k + 1);

  int ptr = 1;

  //memset(f, -0x3f, sizeof(f));

  f[0] = 1e9;

  for (int i = 1; i <= k; ++i) {

    while (t[ptr].a <= q[i].m && ptr <= n) {

      for (int j = 100000; j >= t[ptr].c; --j)

        f[j] = max(f[j],min(f[j - t[ptr].c], t[ptr].b));

      ptr++;

    }

    if (f[q[i].k] > q[i].m + q[i].s)ans[q[i].id] = 1;

  }

  for (int i = 1; i <= k; ++i) {

    if (ans[i]) printf("TAK\n");

    else printf("NIE\n");

  }

  return 0;

}

巴特西

转移顺序的艺术 luogu4394 + lougu2966 + luogu3537

code:

code:

code:

最新文章

热门文章