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

双倍经验？
我写得挺傻，跑得超慢（
进行了大量预处理。

考虑处理出以下值以便 DP： - 设 validi,S 表示能否在第 i 天吃在集合 S 内的菠萝包。 - 设 vali,S 表示在第 i 天吃在集合 S 内的菠萝包对答案的贡献。

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

设 fi,S 表示前 i 天总共吃了集合 S 内的菠萝包的答案。
DP 时枚举 i,S，枚举新吃的组合，即可转移。

由于没有限定吃的天数，可以在转移的同时更新答案。

代码：

#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);
    }
}