hihoCoder#1044 : 状态压缩·一

叁歲伎倆 2022-08-21 03:24 165阅读 0赞

http://hihocoder.com/problemset/problem/1044

#include <iostream>
    using namespace std;
    int N, M, Q;
    int W[1010];
    int dp[1020][1025];
    int countTwo[11] = { 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 };
    int countOne[1030];
    int main()
    {
    	scanf("%d%d%d", &N, &M, &Q);
    	for (int i = 1; i <= N; i++)
    		scanf("%d",&W[i]);
    	for (int i = 0; i <= countTwo[M]; i++)
    	{
    		int count = 0, num = i;
    		while (num != 0)
    		{
    			if (num & 1)
    			{
    				count++;
    			}
    			num = num >> 1;
    		}
    		countOne[i] = count;
    	}
    	int ans = 0;
    	for (int i = 1; i <= N;i++)
    	{
    		for (int j =0; j <1<<M; j++)
    		{
    			int left = j >> 1;
    			int right = (j >> 1) + countTwo[M - 1] + 1;
    			int beforei = dp[i - 1][left] > dp[i - 1][right] ? dp[i - 1][left] : dp[i - 1][right];
    			if (countOne[j] <= Q&&j&1)
    			{
    				dp[i][j] = beforei + W[i];
    				ans = ans > dp[i][j] ? ans : dp[i][j];
    			}
    			else
    				dp[i][j] = beforei;
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关状态压缩动态规划

原文地址：[https://www.cnblogs.com/psephurus-gladius-zdx/p/10581064.html][https_www.cnblogs.

- 日理万妓/ 2022年11月03日 04:04/ 0 赞/ 159 阅读

相关 524 愤怒的小鸟（状态压缩dp-集合式状态压缩dp）

1. 问题描述： Kiana 最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限

Myth丶恋晨/ 2022年09月12日 11:52/ 0 赞/ 187 阅读

相关状态压缩dp

状态压缩dp与状态机模型很相似，都需要通过进一步划分状态使得状态定义更加清楚，状态机模型按照时序来划分集合，状态压缩dp使用二进制数字来划分集合，状态压缩dp一般都需要先预处理

傷城~/ 2022年09月12日 05:56/ 0 赞/ 10 阅读

相关 hihoCoder#1143 : 骨牌覆盖问题·一

快速幂需要注意一个地方，就是别超了数字的范围，及时longlong也很容易爆炸，及时取余才是王道 http://hihocoder.com/problemset/pro

向右看齐/ 2022年08月21日 03:26/ 0 赞/ 119 阅读

相关 hihoCoder#1044 : 状态压缩·一

http://hihocoder.com/problemset/problem/1044 include <iostream> using n

叁歲伎倆/ 2022年08月21日 03:24/ 0 赞/ 166 阅读

相关算法练习系列—hiho1044 状态压缩二(捡垃圾)

题目地址：[http://hihocoder.com/problemset/problem/1044][http_hihocoder.com_problemset_proble

我会带着你远行/ 2022年08月07日 03:59/ 0 赞/ 168 阅读

相关 Hdu 1429（状态压缩）

有钥匙和门的 bfs + 状态压缩一个十把钥匙和锁，分别为a,b......j。当所用的步数小于t即可。和上一篇对应着来看，加强状态压缩的理解。

喜欢ヅ旅行/ 2022年08月05日 08:52/ 0 赞/ 162 阅读

相关 hihocoder #1176 : 欧拉路·一

欧拉路径：无向图存在欧拉路径的条件是：图是联通的（并查集判断pre\[ \]数组根节点的个数）、度数（入度加出度）为奇数的点有且仅有2个或者有0个。

╰半橙微兮°/ 2022年08月02日 15:00/ 0 赞/ 136 阅读

相关论文阅读状态压缩

状态压缩 Abstract 信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被

电玩女神/ 2022年04月23日 09:12/ 0 赞/ 289 阅读

相关 [hihoCoder] 骨牌覆盖问题·一

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：我们有一个2xN的长条形

缺乏、安全感/ 2021年09月17日 14:48/ 0 赞/ 271 阅读