JZOJ 1040 & 1081.「GDOI2007」夏娜的菠萝包

双倍经验?
我写得挺傻,跑得超慢(
进行了大量预处理。

考虑处理出以下值以便 DP:

  • validi,Svalid_{i,S} 表示能否在第 ii 天吃在集合 SS 内的菠萝包。
  • vali,Sval_{i,S} 表示在第 ii 天吃在集合 SS 内的菠萝包对答案的贡献。

这两个东西可以 O(n22n)O(n^2 2^n) 预处理。

fi,Sf_{i,S} 表示 ii 天总共吃了集合 SS 内的菠萝包的答案。
DP 时枚举 i,Si,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
#include <cstdio>
#include <cstring>
#include <algorithm>
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);
}
}