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个位置
输出格式:
一行一个数表示最大可能得到的分数
输入输出样例
5 3 3 1
2 3 3 3 3
2 233
1 3
474
5 3 3 1
111 222 333 444 555
2 52
1 3
1384
6 3 3 2
1 2 3 3 4 1
2 1
1 2
2 2
2 3
16
说明
样例#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[], c[( << ) + ], p[( << ) + ];
int f[][( << ) + ], now, last, ans, g[][( << ) + ]; int main()
{
scanf("%d%d%d%d", &n, &m, &a, &b);
for (int i = ; i <= n; i++)
scanf("%d", &v[i]);
for (int i = ; i <= b; i++)
{
int x, y, stu = ;
scanf("%d%d", &x, &y);
while (x--)
{
int t;
scanf("%d", &t);
stu |= << (a - t);
}
c[stu] += y;
}
for (int i = ; i < ( << a); i++)
for (int j = i; j; j = (j - ) & i)
p[i] += c[j];
memset(f, -0x3f, sizeof(f));
memset(g, -0x3f, sizeof(g));
f[][] = ;
int zhuangtai = ( << a) - ;
for (int i = ; i <= n; i++, swap(f, g), memset(g, -0x3f, sizeof(g)))
for (int j = ; j <= min(m, i); j++)
for (int s = ; s <= zhuangtai; s++)
if (f[j][s] != -)
{
int t = (s << ) & zhuangtai;
g[j][t] = max(g[j][t], f[j][s] + (i >= a ? p[t] : ));
g[j + ][t | ] = max(g[j + ][t | ], f[j][s] + v[i] + (i >= a ? p[t | ] : ));
}
for (int i = ; i <= m; i++)
for (int j = ; j < ( << a); j++)
ans = max(ans, f[i][j]);
printf("%d\n", ans); return ;
}
最新文章
- OC ---- 字典集合 iOS学习-----细碎知识点总结
- Android相关sdk使用
- JavaScript中给对象添加函数的方式
- SpringMVC中使用Jcaptcha实现校验码验证
- 为什么浏览器User-agent总是有Mozilla字样(User-agent String里的历史故事)【搜藏】
- 使用C#或javascript将Table里的数据导出到Excel
- word vbs脚本 设置所有题注样式为蓝色,下划线
- websocket简介
- 关于对MVC和MVVM的思考
- windows10 uwp获取设备当前地理位置(经纬度)
- python科学计算
- socket 编程中。 服务端用到多线程
- how to tell gcc with c99 enable
- [转]curl的详细使用
- PHP 操作 Redis 的手册
- JavaWeb--简单分页技术
- Go Example--通道同步
- D3.js的基础部分之数组的处理 数组的排序和求值(v3版本)
- 试题 D: 数的分解 蓝桥杯
- GeneXus学习笔记——创建一个知识库 哈哈哈哈!
热门文章
- B4197 [Noi2015]寿司晚宴 状压dp
- luoguP2939 [USACO09FEB]改造路Revamping Trails
- Tyvj 1068 巧用扩展KMP
- 第四周 Leetcode 124. Binary Tree Maximum Path Sum (HARD)
- vue项目打包之后首页白屏的问题
- Nginx网站用Let’sEncrypt证书开HTTPS
- ubuntu 更显列表 [Connecting to archive.ubuntu.com (2001:67c:1360:8001::21)] 超时的解决方法
- Coursera公开课-Machine_learing:编程作业4
- IC验证概念总结
- JS高级——逻辑中断