noip模拟赛时之终末

题目背景

圣乔治：不用拘泥，剩下的时间已不多……

圣乔治：直呼我的真名——

丝佩碧雅：圣乔治大人

圣乔治：如今，已无法维持结界，或是抑制深渊的前进

圣乔治：既然如此，我将献上这副身躯，期望最后的战斗

圣乔治：已经——应该没有再和我多需说明的话语了

圣乔治：我也明白，我和其他4人都一样，是没有内在的傀儡——只不过是曾经存在的幻影罢了……

圣乔治：我本就是，身体被禁忌之龙的诅咒吞噬殆尽，几乎半生不死的状态……

圣乔治：曾经那个被称作虹之圣乔治的男人已经死了

圣乔治：我除了消灭虚无的碎片，消灭那个魔女以外，已别无他望……

丝佩碧雅：我曾经爱过你，圣乔治大人——

美玲：快走，她由我来挡住！

美玲：你们快去打倒虹之圣乔治和莉泽洛特！

我的脊髓与头被一分为二——

跌入黑暗的那一刹那——

我，呼唤着，他的名字——

圣乔治……大人……

为了朋友和明天——

我们是同伴……我这样相信着

因为是同伴……所以相信你……

题目描述

吊打集训队的zcy

给你出了一道题：

给你一个长为n的序列v，你可以从里面选出最多m个数

有一个数a，以及b个规则，每个规则即为：

对于这个序列的所有长为a的连续子区间，

如果这个子区间中对应的给出的x个位置都被选中了，

则这次选择的分数加上y（y可能为负数，这种情况下分数仍然要加上y）

输入输出格式

输入格式：

第一行四个数n,m,a,b

之后一行n个数表示序列v

之后输入b个规则

每个规则先输入两个数x和y，x != 0

之后一行x个数，分别表示这给定的x个位置

输出格式：

一行一个数表示最大可能得到的分数

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

5 3 3 1
111 222 333 444 555
2 52
1 3

输出样例#2：

输入样例#3：

6 3 3 2
1 2 3 3 4 1
2 1
1 2
2 2
2 3

输出样例#3：

说明

样例#4，#5，#6见下发的文件

【子任务】

子任务会给出部分测试数据的特点。

如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

测试点编号	n的范围	m的范围	a的范围	b的范围
测试点1	n <= 20	m <= 20	a <= 10	b <= 5
测试点2	n <= 20	m <= 20	a <= 10	b <= 5
测试点3	n <= 40	m <= 40	a <= 10	b <= 100000
测试点4	n <= 40	m <= 40	a <= 10	b <= 100000
测试点5	n <= 100	m <= 50	a <= 10	b = 0
测试点6	n <= 100	m <= 50	a <= 10	b = 0
测试点7	n <= 100	m <= 50	a <= 10	b <= 100000
测试点8	n <= 100	m <= 50	a <= 10	b <= 100000
测试点9	n <= 100	m <= 50	a <= 16	b <= 100000
测试点10	n <= 100	m <= 50	a <= 16	b <= 100000

对于100%的数据，n <= 100 , m <= 50 ，a <= 16 , b <= 100000 ，序列中每个值以及每条规则带来的加分的绝对值 <= 100

【说明】

【样例1说明】

【样例2说明】

【样例3说明】

分析：一开始想着贪心，但是贪不出来.仔细观察题目就会发现，这其实就是状压dp.因为a <= 16,我们可以状压a.先预处理出每个状态的贡献值.设f[i][j][k]为前i个数中选了j个末尾a个的状态为k的分数，枚举i-1位置上末尾a个的状态s,那么当前如果不考虑第i位的状态t就是(s << 1) & ((1 << a) - 1).如果第i位不选,那么f[i][j][t] = max{f[i][j][t],f[i - 1][j][s] + p[t]},p是预处理出的每个状态的贡献值，如果第i位要选，那么f[i][j][t | 1] = max{f[i][j][t | 1],f[i-1][j-1][s] + v[i] + p[t | 1]}

因为i是从i-1转移过来的，所以可以用滚动数组优化一下.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m, a, b, v[110], c[(1 << 16) + 10], p[(1 << 16) + 10];
int f[55][(1 << 16) + 10], now, last, ans, g[55][(1 << 16) + 10];

int main()
{
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    for (int i = 1; i <= b; i++)
    {
        int x, y, stu = 0;
        scanf("%d%d", &x, &y);
        while (x--)
        {
            int t;
            scanf("%d", &t);
            stu |= 1 << (a - t);
        }
        c[stu] += y;
    }
    for (int i = 0; i < (1 << a); i++)
        for (int j = i; j; j = (j - 1) & i)
            p[i] += c[j];
    memset(f, -0x3f, sizeof(f));
    memset(g, -0x3f, sizeof(g));
    f[0][0] = 0;
    int zhuangtai = (1 << a) - 1;
    for (int i = 1; i <= n; i++, swap(f, g), memset(g, -0x3f, sizeof(g)))
        for (int j = 0; j <= min(m, i); j++)
            for (int s = 0; s <= zhuangtai; s++)
                if (f[j][s] != -1044266559)
                {
                    int t = (s << 1) & zhuangtai;
                    g[j][t] = max(g[j][t], f[j][s] + (i >= a ? p[t] : 0));
                    g[j + 1][t | 1] = max(g[j + 1][t | 1], f[j][s] + v[i] + (i >= a ? p[t | 1] : 0));
                }
    for (int i = 0; i <= m; i++)
        for (int j = 0; j < (1 << a); j++)
            ans = max(ans, f[i][j]);
    printf("%d
", ans);

    return 0;
}