题意:有 $n (n \leq 20) $ 道题 第 $i$ 道题完成之前需要完成 $p_1..p_{s_i}$ 道题 已经完成 $x-1$ 题后做第 $i$ 道题的收益是 $a_i*x+b_i$(可能有负数) 每分钟可以完成一道题 求最大的得分
出题人我……&*%……&¥%…… ,把真题意放在括号里。没有说明必须从第一分钟开始连续做题,导致在第一句话前提下看第二题很容易想成可以某分钟不做题

然后跟错误题意刚了两个小时。。

(场外OB 给别人写的,真打比赛怕是要丢掉这个题

屑题

题解:由 $p_i$ 向 $i$ 连有向边,设 $h[i]$ 表示做第 $i$ 道题的先决条件,先拓扑排序,把环去掉,同时利用DAG性质更新 $h[i]$ 即 $h[v]$ $|= h[u]$ 然后预处理一下合法状态 $f[i][S]$ 表示第 $i$ 步做的题是集合 $S$ 的最大收益

需要滚动数组

细节有点多。。。(对我这种菜鸡来说)

我可能写麻烦了,看到有很短的代码

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

typedef double lf;
typedef long long ll;
typedef long double llf;
typedef pair<ll, ll> pll;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef unsigned long long ull;

bool Debug;
const int mod = 1e9 + 7, MAXN = 1e5 + 7, inft = 1e9;
const ll infl = 1ll << 60;

#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define mset(a, b) memset(a, b, sizeof(a))
#define debug(...) if (Debug) fprintf(stderr, __VA_ARGS__)
#define lop(i,a,b) for(int i = (a), i##end = (b); i <= i##end; ++i)
#define dlop(i,a,b) for(int i = (a), i##end = (b); i >= i##end; --i)
#define ergo(a) for(__typeof(a.end())it = (a).begin(), it##end = (a).end(); it != it##end; ++it)

template<class A, class B> void chmax(A &x, B y) {if (x < y) x = y;}
template<class A, class B> void chmin(A &x, B y) {if (x > y) x = y;}
template<class A, class B> A max(A a, B b) {return a > b ? a : b;}
template<class A, class B> A min(A a, B b) {return a < b ? a : b;}
template<class A, class B> A gcd(A a, B b) {if (a < b) swap(a, b); if (!b) return a; while (A t = a % b) a = b, b = t; return b;}
template<class A, class B> A lcm(A a, B b) {return a / gcd(a, b) * b;}
template<class A, class B> A Pow(A a, B b) {A ret = 1; for ( ; b; b >>= 1) {if (b & 1) ret = ret * 1ll * a % mod; a = a * 1ll * a % mod;} return ret % mod;}
template<class T> inline T abs(T x) {return x >= 0 ? x : -x;}
template<class T> inline T sqr(T x) {return x * x;}

bool IS(int x) {return x == 10 || x == 13 || x == ' ';}

struct IO {
  struct Cg {inline int operator()() {return getchar();}};
  struct Cp {inline void operator()(int x) {putchar(x);}};
#define OP operator
#define RT return *this
#define RX x=0;int t=P();while((t<'0'||t>'9')&&t!='-')t=P();f=1;\
if(t=='-')t=P(),f=-1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f==-1)x=-x;
#define RU x=0;int t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x
  template<typename T>struct Fr {int f; T P; inline Fr&OP, (int&x) {RX; x *= f; RT;} inline OP int() {int x; TR;} inline Fr&OP, (ll &x) {RX; x *= f; RT;} inline OP ll() {ll x; TR;} inline Fr&OP, (char&x) {for (x = P(); IS(x); x = P()); RT;} inline OP char() {char x; TR;} inline Fr&OP, (char*x) {char t = P(); for (; IS(t); t = P()); if (~t) {for (; !IS(t) && ~t; t = P()) * x++ = t;}*x++ = 0; RT;} inline Fr&OP, (lf&x) {RX; RL; RT;} inline OP lf() {lf x; TR;} inline Fr&OP, (llf&x) {RX; RL; RT;} inline OP llf() {llf x; TR;} inline Fr&OP, (uint&x) {RU; RT;} inline OP uint() {uint x; TR;} inline Fr&OP, (ull&x) {RU; RT;} inline OP ull() {ull x; TR;}};
  Fr<Cg>in;
#define WI if(x){if(x<0)P('-'),x=-x;c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU if(x){c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
  template<typename T>struct Fw {int c, s[24]; T P; inline Fw&OP, (int x) {WI; RT;} inline Fw&OP()(int x) {WI; RT;} inline Fw&OP, (uint x) {WU; RT;} inline Fw&OP()(uint x) {WU; RT;} inline Fw&OP, (ll x) {WI; RT;} inline Fw&OP()(ll x) {WI; RT;} inline Fw&OP, (ull x) {WU; RT;} inline Fw&OP()(ull x) {WU; RT;} inline Fw&OP, (char x) {P(x); RT;} inline Fw&OP()(char x) {P(x); RT;} inline Fw&OP, (const char*x) {while (*x)P(*x++); RT;} inline Fw&OP()(const char*x) {while (*x)P(*x++); RT;} inline Fw&OP()(lf x, int y) {WL; RT;} inline Fw&OP()(llf x, int y) {WL; RT;}};
  Fw<Cp>out;
} io;
#define in io.in
#define out io.out

ll f[2][1<<20];

struct Edge {
  int v, next;
}G[21*23]; int head[21], tot, s[21], a[21], b[21], n, ind[21], topo[21], cnt, h[21], tmp, Cnt[1<<20];

bool ok[1 << 20];
ll ans;
inline int Count(int x) {
  int ret = 0;
  while(x) {ret += x & 1;x >>= 1;}
  return ret;
}
void add(int u, int v) {
  G[++tot] = (Edge) {v, head[u]}; head[u] = tot;
  ++ind[v];
}
int na[21], nb[21], ns[21], nh[21];

void toposort() {
  lop(i,1,n) if (!ind[i]) topo[++cnt] = i;
  for(int u = 1; u <= cnt; ++u) 
    for(int i = head[topo[u]]; i; i = G[i].next) {
      int v = G[i].v;
      if (--ind[v] == 0) topo[++cnt] = v;
      h[v] |= h[topo[u]];
    }
  for(int i = 1; i <= cnt; ++i) {
    na[i] = a[topo[i]], nb[i] = b[topo[i]], ns[i] = s[topo[i]], nh[i] = h[topo[i]];
  }
  swap(na, a), swap(nb, b),swap(ns, s), swap(nh, h);
  n = cnt;
}

int main() {
  in, n;
  lop(i,1,n) {
    in, a[i], b[i], s[i];
    lop(j,1,s[i]) {
      in, tmp;
      add(tmp, i), h[i] |= (1 << tmp - 1);
    }
  }  
  toposort();
  for(int i = 0; i < (1 << n); ++i) {
    ok[i] = 1;
    Cnt[i] = Count(i);
    for (int j = 1; j <= n; ++j) if (((1 << j-1) & i) && (h[j] & i) != h[j]) {ok[i] = 0; break;}
  }
  lop(i,0,n-1) {
    bool p = i & 1;
    for(int j = 0; j < (1 << n); ++j) {
      if (Cnt[j] > i || !ok[j]) continue;
      for(int k = 1; k <= n; ++k) {
        if ((j & (1 << k-1)) || !ok[j | (1 << k-1)]) continue;
        chmax(f[!p][j | (1 << k-1)], f[p][j] + 1ll * a[k] * (Cnt[j]+1) + b[k]);
      }
      chmax(f[!p][j], f[p][j]);
      assert(f[!p][j] >= 0);
    }
  }
  for(int j = 0; j < (1 << n); ++j) chmax(ans, f[n&1][j]);
  out, ans;
  return 0;
}

/*
5
5 6 0
4 5 1 1
3 4 1 2
2 3 1 3
1 2 1 4
*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注