AC Challenge(状态压缩DP)

2024-02-10 16:48
文章标签 dp 压缩 状态 ac challenge

本文主要是介绍AC Challenge(状态压缩DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Dlsj is competing in a contest with n (0 < n \le 20)n(0<n≤20) problems. And he knows the answer of all of these problems.

However, he can submit ii-th problem if and only if he has submitted (and passed, of course) s_isi​ problems, the p_{i, 1}pi,1​-th, p_{i, 2}pi,2​-th, ......, p_{i, s_i}pi,si​​-th problem before.(0 < p_{i, j} \le n,0 < j \le s_i,0 < i \le n)(0<pi,j​≤n,0<j≤si​,0<i≤n) After the submit of a problem, he has to wait for one minute, or cooling down time to submit another problem. As soon as the cooling down phase ended, he will submit his solution (and get "Accepted" of course) for the next problem he selected to solve or he will say that the contest is too easy and leave the arena.

"I wonder if I can leave the contest arena when the problems are too easy for me."
"No problem."
—— CCF NOI Problem set

If he submits and passes the ii-th problem on tt-th minute(or the tt-th problem he solve is problem ii), he can get t \times a_i + b_it×ai​+bi​ points. (|a_i|, |b_i| \le 10^9)(∣ai​∣,∣bi​∣≤109).

Your task is to calculate the maximum number of points he can get in the contest.

Input

The first line of input contains an integer, nn, which is the number of problems.

Then follows nn lines, the ii-th line contains s_i + 3si​+3 integers, a_i,b_i,s_i,p_1,p_2,...,p_{s_i}ai​,bi​,si​,p1​,p2​,...,psi​​as described in the description above.

Output

Output one line with one integer, the maximum number of points he can get in the contest.

Hint

In the first sample.

On the first minute, Dlsj submitted the first problem, and get 1 \times 5 + 6 = 111×5+6=11 points.

On the second minute, Dlsj submitted the second problem, and get 2 \times 4 + 5 = 132×4+5=13 points.

On the third minute, Dlsj submitted the third problem, and get 3 \times 3 + 4 = 133×3+4=13 points.

On the forth minute, Dlsj submitted the forth problem, and get 4 \times 2 + 3 = 114×2+3=11 points.

On the fifth minute, Dlsj submitted the fifth problem, and get 5 \times 1 + 2 = 75×1+2=7 points.

So he can get 11+13+13+11+7=5511+13+13+11+7=55 points in total.

In the second sample, you should note that he doesn't have to solve all the problems.

样例输入1复制

5
5 6 0
4 5 1 1
3 4 1 2
2 3 1 3
1 2 1 4

样例输出1复制

55

样例输入2复制

1
-100 0 0

样例输出2复制

0

题目来源

ACM-ICPC 2018 南京赛区网络预赛

题意:有n个问题,做第i个问题得分是t*a[i]+b[i](t是第几个做的题),但是做第i题之前还需要先做其他的一些题目....可以选择不做完所有的题,问最后的最高得分.

题解:一开始的思路是有依赖的树形背包问题,但是这道题还是有些诡异的,因为可以成环,所以给的不一定是一颗树,队友想到了应该是一道状压DP的问题,因为n只有20,所以状态最多1e6种,复杂度O(n*2^n),枚举所有可能的状态,并从中选择一个物品看是否这个物品需要的状态是当前枚举状态去掉这个物品状态的子集,若是,则可以进行转移。

#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define SI(i) scanf("%lld",&i)
#define PI(i) printf("%lld\n",i)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int MAX=2e6+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int dir[9][2]={0,1,0,-1,1,0,-1,0, -1,-1,-1,1,1,-1,1,1};
template<class T>bool gmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>bool gmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>void gmod(T &a,T b){a=((a+b)%mod+mod)%mod;}
typedef pair<ll,ll> PII;int p[30],a[30],b[30];
ll dp[MAX];
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++){int t;scanf("%d%d%d",&a[i],&b[i],&t);while(t--){int x;scanf("%d",&x);p[i]|=(1<<x-1);//printf("%d\n",p[i]);}}for(int i=0;i<(1<<n);i++)dp[i]=-1e16;dp[0]=0;for(int i=0;i<(1<<n);i++){int t=0;for(int j=0;j<n;j++)if(i&(1<<j)) t++;for(int j=0;j<n;j++) //枚举加入哪一个if(i&(1<<j) && (i&p[j])==p[j]){gmax(dp[i],dp[(1<<j)^i]+1LL*t*a[j]+b[j]);// printf("%d %lld\n",(1<<j)^i,dp[i]);}}ll ans=0;for(int i=0;i<(1<<n);i++)gmax(ans,dp[i]);printf("%lld\n",ans);return 0;
}

 

这篇关于AC Challenge(状态压缩DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/697590

相关文章

使用Python实现IP地址和端口状态检测与监控

《使用Python实现IP地址和端口状态检测与监控》在网络运维和服务器管理中,IP地址和端口的可用性监控是保障业务连续性的基础需求,本文将带你用Python从零打造一个高可用IP监控系统,感兴趣的小伙... 目录概述:为什么需要IP监控系统使用步骤说明1. 环境准备2. 系统部署3. 核心功能配置系统效果展

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

关于WebSocket协议状态码解析

《关于WebSocket协议状态码解析》:本文主要介绍关于WebSocket协议状态码的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录WebSocket协议状态码解析1. 引言2. WebSocket协议状态码概述3. WebSocket协议状态码详解3

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn