首页 > 其他分享 >GYM 103389 C

GYM 103389 C

时间:2024-09-14 17:13:20浏览次数:8  
标签:cnt int GYM 状压 tot 103389 MAXN id

题目描述

有 \(N\) 个景点,第 \(i\) 个属于公司 \(c_i\)。当你第一次路过一个属于公司 \(i\) 的景点时,你会获得 \(w_i\) 元。

在景点之间有 \(m\) 条单向道路连接 \(u,v(u<v)\)。一开始你在景点 \(1\)。求到所有景点 \(1\le i\le N\) 时最多能获得多少元。

思路

由于公司数量很少,所以考虑状压。

如果直接状压的话很好想到。但这里 \(N\le 36\),似乎只用加一点点优化就行了。

而这里状压是记录哪些公司被访问过了。但我们的目的是为了不重复统计一个公司的贡献。所以只需记录出现次数 \(\ge 2\) 的公司即可。

总共记录的只有 \(\frac{N}{2}=18\),可以接受。

空间复杂度 \(O(2^{\frac{N}{2}} \cdot N)\),时间复杂度 \(O(2^{\frac{N}{2}} \cdot N^2)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 40, INF = 40000001;

int n, m, c[MAXN], w[MAXN], cnt[MAXN], _id[MAXN], tot, dp[MAXN][1 << 18], g[MAXN][MAXN];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    cin >> c[i];
    cnt[c[i]]++;
  }
  for(int i = 1; i <= n; ++i) {
    cin >> w[i];
    if(cnt[i] > 1) {
      tot++;
      _id[i] = tot - 1;
    }
  }
  for(int i = 1, u, v; i <= m; ++i) {
    cin >> u >> v;
    g[u][v] = 1;
  }
  for(int i = 1; i <= n; ++i) {
    for(int j = 0; j < (1 << tot); ++j) {
      dp[i][j] = -INF;
    }
  }
  dp[1][(cnt[c[1]] > 1 ? (1 << _id[c[1]]) : 0)] = w[c[1]];
  for(int i = 1; i <= n; ++i) {
    int Max = 0;
    for(int j = 0; j < (1 << tot); ++j) {
      if(dp[i][j] < 0) {
        continue;
      }
      Max = max(Max, dp[i][j]);
      for(int v = 1; v <= n; ++v) {
        if(g[i][v]) {
          dp[v][j | (cnt[c[v]] > 1 ? (1 << _id[c[v]]) : 0)] = max(dp[v][j | (cnt[c[v]] > 1 ? (1 << _id[c[v]]) : 0)], dp[i][j] + (cnt[c[v]] <= 1 || !((j >> _id[c[v]]) & 1) ? w[c[v]] : 0));
        }
      }
    }
    cout << Max << "\n";
  }
  return 0;
}

标签:cnt,int,GYM,状压,tot,103389,MAXN,id
From: https://www.cnblogs.com/yaosicheng124/p/18414383

相关文章

  • GYM 104114 F
    题目描述有\(N\)个参赛选手,将进行\(N-1\)场比赛,第\(i,j\)个选手进行比赛有\(P_{i,j}\)的激烈程度。每当选手\(i\)打败选手\(j\)时,\(P_{i,x}\leftarrow\max(P_{i,x},P_{j.x})\)。在这些比赛中,编号小的选手总是打败编号大的选手。求最终\(N-1\)场比赛的激烈程度之和......
  • OpenAI Gym ProcGen - Getting Action Meanings
    题意:OpenAIGymProcGen-获取动作含义问题背景:IntheOpenAIProcGengym,Iamnotgettingaway togetthemeaningsoftheactionvalues,Icanseethatthereare15actionsforthecoinrunenvironmentusing env.action_space.n.IhavetriedboththeG......
  • GYM 105264 E
    题目描述给定一个\(N\)个点的树,你要从中选出一个大小为\(k\)的子树出来,求这个子树的最小直径。思路由于此题允许\(O(N^2)\)的时间复杂度,所以考虑枚举子树的中心。接着以该中心为根向下搜出深度为\(i\)的结点数\(cnt_i\),接着枚举直径长度除\(2\)。由于这里直径可能长......
  • GYM 105264 C
    题目描述给定一个长度为\(N\)的数组\(A\),每次你可以令\(A_i\leftarrowA_i+1\)或\(A_i-1\)。求进行至多\(k\)次操作后\(A\)中最少不同元素数量。思路首先对\(A\)进行排序。令\(dp_{i,j}\)表示考虑前\(i\)个数,有\(j\)个不同的值时最多还能剩余几次操作。很......
  • OpenAI Gym custom environment: Discrete observation space with real values
    题意:OpenAIGym自定义环境:具有实数值的离散观测空间问题背景:Iwouldliketocreatecustomopenaigymenvironmentthathasdiscretestatespace,butwithfloatvalues.Tobemoreprecise,itshouldbearangeofvalueswith0.25step:10.0,10.25,10.5,10......
  • Start OpenAI gym on arbitrary initial state
    题意:“在任意初始状态下启动OpenAIGym”问题背景:AnybodyknowsanyOpenAIGymenvironmentswherewecansettheinitialstateofthegame?Forexample,IfoundtheMountainCarContinuous-v0candosuchthingsothatwecanselectatwhichpointthecarst......
  • gym创建环境、自定义gym环境
    环境:half_cheetah.pyfromosimportpathimportnumpyasnpfromgymnasiumimportutilsfromgymnasium.envs.mujocoimportMujocoEnvfromgymnasium.spacesimportBoxDEFAULT_CAMERA_CONFIG={"distance":4.0,}classMOHalfCheetahEnv(Mujoc......
  • gym序列化、EzPickle类
    EzPickle是一个用于强化学习环境的类,它重写了__getstate__和__setstate__方法,以便通过构造函数参数(*args,**kwargs)进行序列化和反序列化。这个设计允许那些无法直接用pickle库处理的对象,如数据库连接和网络套接字,也能在保存和恢复时保持其状态。"""Classforpicklingandun......
  • mujoco gymnasium 环境
    本文简要介绍gynasium中基于mujoco的环境搭建。参照gynasium.envs.mujoco。1.gynasium.Env简介在gynasium中,环境基类为gynasium.Env,其中定义了step,reset,render,close等方法以及action_space,observation_space,reward_range,spec,metadata,np_random......
  • Why unwrap an openAI gym?
    题意:为什么要“解开”OpenAIGym?问题背景:I'mtryingtogetsomeinsightsintoreinforcementlearningwhileusingopenAIgymasalearningenvironment.Idothisbyreadingthebook Hands-onreinforcementlearningwithPython.Inthisbook,somecodeisp......