双倍经验？
我写得挺傻，跑得超慢（
进行了大量预处理。
考虑处理出以下值以便 DP： - 设 \(valid_{i,S}\) 表示能否在第 \(i\) 天吃在集合 \(S\) 内的菠萝包。 - 设 \(val_{i,S}\) 表示在第 \(i\) 天吃在集合 \(S\) 内的菠萝包对答案的贡献。
这两个东西可以 \(O(n^2 2^n)\) 预处理。
设 \(f_{i,S}\) 表示前 \(i\) 天总共吃了集合 \(S\) 内的菠萝包的答案。
DP 时枚举 \(i,S\)，枚举新吃的组合，即可转移。
由于没有限定吃的天数，可以在转移的同时更新答案。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const int N = 14;
const int M = 20;
int n,m,full;
int a[N + 5],d[N + 5];
int k[M + 5],v[M + 5],e[M + 5];
int f[N + 5][(1 << N) + 5],valid[N + 5][(1 << N) + 5],val[N + 5][(1 << N) + 5];
int ans;
int main()
{
while(scanf("%d",&n),n)
{
full = (1 << n) - 1;
for(register int i = 1;i <= n;++i)
scanf("%d%d",a + i,d + i);
scanf("%d",&m);
for(register int i = 1;i <= m;++i)
{
scanf("%d%d",k + i,e + i),v[i] = 0;
int x;
for(register int j = 1;j <= k[i];++j)
scanf("%d",&x),v[i] |= (1 << x - 1);
}
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= full;++j)
valid[i][j] = 1,val[i][j] = 0,f[i][j] = -0x3f3f3f3f;
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= full;++j)
for(register int k = 1;k <= n;++k)
if(j & (1 << k - 1))
{
valid[i][j] &= a[k] - d[k] * (i - 1) >= 0;
val[i][j] += a[k] - d[k] * (i - 1);
}
ans = f[0][0] = 0;
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= full;++j)
for(register int k = 1;k <= m;++k)
if(valid[i][v[k]] && !(j & v[k]))
{
f[i][j | v[k]] = max(f[i][j | v[k]],f[i - 1][j] + e[k] + val[i][v[k]]);
ans = max(ans,f[i][j | v[k]]);
}
printf("%d\n",ans);
}
}