状压dp

‌问题分析

• 有N个游戏币(1≤N≤16)，M个顺序关卡（状压的算盘都崩脸上了）
• 游戏币可以任意顺序使用，关卡必须按顺序闯
• 目标是最大化剩余游戏币的总价值

思路

因为游戏币顺序随便，考虑枚举当前已经用了哪些游戏币

• ‌状态设计：‌dp[i]表示使用i对应的游戏币组合时，能闯到的最大关卡数（闯的越多，浪费的越少）

i是一个n位二进制数，1表示用过，0表示没用过

• 预处理：对每个游戏币，预处理从各关卡开始能闯到的最大关卡

lef[j][st]：游戏币j，从st关开始闯，最多闯完第多少关，j和st见下文

• 状态转移‌：枚举最后使用的游戏币进行转移
• 答案统计‌：当某个状态能闯完所有关卡时，统计剩余游戏币价值

转移具体实现

已知一个状态i，枚举最后一次用的游戏币j ((i&(1<<(j-1)))==1)（翻译成人话：j在i状态下被选了）

st = dp[(i^(1<<(j-1)))]+1;

dp[i] = max(dp[i], lef[j][st]);

代码也有一些注释辅助理解

code

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define look_memory cerr<<abs(&M1-&M2)/1024.0/1024<<"MB\n";

namespace syr
{
	const ll N = 20;
	const ll M = 1e5+10;
	const ll P = (1<<16)+10;
	ll n, m, ans;
	ll a[N], b[M];
	ll lef[N][M]; //第i个币，从j关开始闯，闯完第几关 
	ll dp[P]; //用了哪些币 闯完第几关 
	void init () {
		for (ll i=1; i<=n; i++) { //枚举币 
			for (ll l=1, r=0; l<=m; l++) { //可以从l闯到r关 
				while (b[r]-b[l-1]<=a[i] && r<=m) r++; //能闯就一路闯下去（反正找的是最多闯到哪） 
				r--; //第r关是闯不完的，要-- 
				if (l>r) continue; //一关都闯不了（太惨了TAT） 
				lef[i][l] = r; 
			}
		}
	} 
	void update (ll i) { //更新答案 
		ll sum = 0; //剩余的点数  
		for (ll k=1; k<=n; k++)
			if (!(i&(1<<(k-1)))) sum+=a[k]; //没用这个币，就把他加到剩余里  
		ans = max(ans, sum); //更新剩余点数最大值 
	}
	void work()
	{
		cin>>n>>m;
		for (ll i=1; i<=n; i++) cin>>a[i];
		for (ll i=1; i<=m; i++) {
			cin>>b[i];
			b[i] += b[i-1]; //前缀和处理闯关的消耗（方便后面双指针用） 
		}
		init(); //双指针预处理  
		memset(dp, -0x3f, sizeof(dp)); //一定不要初始化成0！！！（因为答案可能为0） 
		ans = dp[0]; //给ans初始化极小值  
		dp[0] = 0; //一个币都不用闯完0关 
		for (ll i=1; i<=n; i++) //初始化用一个币的情况 
			dp[(1<<(i-1))] = lef[i][1]; //i从1开始的 (1==(1<<0)) 所以是1<<(i-1) 
		for (ll i=1; i<(1<<n); i++) { //用了的游戏币  
			for (ll j=1; j<=n; j++) { //最后用的哪个 
				if (!(i&(1<<(j-1)))) continue;
				ll st = dp[(i^(1<<(j-1)))]+1; //从哪一关开始闯，因为上次已经闯完这一关了， 所以+1  
				dp[i] = max(dp[i], lef[j][st]); //最多闯完第几关 
				if (dp[i]>=m) update(i);
			}
		}
		if (ans>=0) cout<<ans; //注意是>=（有'='！！！！）（怎么不能一个币都不剩呢。。。） 
		else cout<<-1;
	}
}

bool M2;

int main()
{
//	freopen("game.in", "r", stdin);
//	freopen("game.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(0);
	look_memory;
	syr::work();
	return 0;
}