南京网络赛E题（状压）

清疚 2022-05-14 03:27 207阅读 0赞

[传送门][Link 1]

dp\[i\]代表i二进制代表的的题目全做完的最大值。

dp\[i\]=max(dp\[i\], dp\[pre\]+a\[i\]\*num\[i\]+b\[i\])   pre是去掉一题的前一个状态。

重要的是初始化，对于不可能转移到的状态要置为-INF

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+1e5;
    typedef long long ll;
    ll dp[N], n, a[30], b[30], s[30], num[N];
    
    int main(){
        scanf("%d", &n);
        int cnt, pre;
        for(int i=1; i<=n; i++){
            scanf("%lld%lld%d", &a[i], &b[i], &cnt);
            for(int j=1; j<=cnt; j++){
                scanf("%d", &pre);
                s[i]|=1<<(pre-1);
            }
        }
    
        int up=1<<n;
        ll ans=0;
        for(int i=1; i<=up; i++) num[i]=__builtin_popcount(i);
        for(int i=1; i<=up; i++) dp[i]=-1e18;
        for(int i=0; i<up; i++){
            int st=i; cnt=1;
            while(st){
                if(st&1){
                    int pr=i^(1<<(cnt-1));
                    if((pr&s[cnt])==s[cnt]){
                        dp[i]=max(dp[i], dp[pr]+a[cnt]*num[i] + b[cnt]);
                    }
                }
                cnt++;
                st>>=1;
            }
        }
    
        for(int i=0; i<up; i++)
            ans=max(ans, dp[i]);
    
        printf("%lld\n", ans);
    
        return 0;
    }

[Link 1]: https://nanti.jisuanke.com/t/30994

发表评论取消回复

表情：

评论列表（有 0 条评论，207人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压+概率DP】CF678 E

[Problem - E - Codeforces][] 题意： ![460fa11fa21742e4873f90d5cd114ad9.png][] 思路：首先，n

绝地灬酷狼/ 2024年03月24日 23:46/ 0 赞/ 89 阅读

相关【子序列+状压DP】ABC308 E MEX

这应该算是很套路的题，照理说是要做出来的 [E - MEX (atcoder.jp)][E - MEX _atcoder.jp] 题意： ![e6a5990b05cf48

雨点打透心脏的1/2处/ 2024年03月17日 13:55/ 0 赞/ 61 阅读

相关【状压DP】2021ccpc女生赛 C 连锁商店

[Problem - C - Codeforces][] 题意： ![114e591cb2614aeaaa4c482dd11f9021.png][] 思路：一开始想的

深藏阁楼爱情的钟/ 2024年03月17日 09:25/ 0 赞/ 66 阅读

相关 2019 ICPC 南京网络赛

A. 00:40:35 solved by hl 很显然需要一种方法O(1)定位x,y上的数字，利用矩阵的规律可以找到然后就是一个子矩阵和问题，小范围可以直接二维前

短命女/ 2023年10月10日 07:49/ 0 赞/ 81 阅读

相关 Codeforces 1215E 状压DP

题意：给你一个序列，你可以交换序列中的相邻的两个元素，问最少需要交换多少次可以让这个序列变成若干个极大的颜色相同的子段。思路：由于题目中的颜色种类很少，考虑状压DP。设dp

ゞ浴缸里的玫瑰/ 2023年08月17日 17:22/ 0 赞/ 173 阅读

相关 Robots 2019南京网络赛（概率dp）

Robots \\\[ Time Limit: 1000 ms \\quad Memory Limit: 262144 kB \\\] 题意有一个机器人要从 \

曾经终败给现在/ 2023年08月17日 17:04/ 0 赞/ 71 阅读

相关 2019ACM-ICPC南京网络赛Holy Grail （SPFA / Floyd 模板题）

Holy Grail 限制 1000 ms 256 MB As the current heir of a wizarding family with a long h

冷不防/ 2023年06月05日 12:33/ 0 赞/ 22 阅读

相关广东工业大学网络赛E题思维题

Problem E: 积木积水 Description 现有一堆边长为1的已经放置好的积木，小明（对的，你没看错，的确是陪伴我们成长的那个小明）想知道当下雨天来时会

阳光穿透心脏的1/2处/ 2022年07月30日 13:15/ 0 赞/ 319 阅读

相关南京网络赛E题（状压）

[传送门][Link 1] dp\[i\]代表i二进制代表的的题目全做完的最大值。 dp\[i\]=max(dp\[i\], dp\[pre\]+a\[i\]\num\[i

清疚/ 2022年05月14日 03:27/ 0 赞/ 208 阅读

相关南京现场赛总结

南京现场赛就这么结束了，心情很复杂。。首先十分感谢魏神和萌神，冒着被我坑的风险打了一场。。而且十分不幸的是，我确实坑了他们。。。比赛的气氛很好，而且参赛队员之间的氛围也

落日映苍穹つ/ 2022年05月13日 00:06/ 0 赞/ 210 阅读