牛客-946B-筱玛爱阅读

题意

n本书, 对应n个价格标签, 你可以随便改变价格标签的顺序
m个优惠方案, 每个方案, 可以让这个方案中, 价格最小的那本书免费

要买完这n本书, 且每本书只能买一次, 问最小花费是多少?

思路

如果标签价格固定, 直接枚举购买的方案即可, 见代码1

现在价格不固定
考虑一个i本书的方案, 能够免费的最大价值就是, 第i大的书本价格 (将这i本书, 贴上前i大的价格 )
再考虑一个j本书的方案, 能够免费的最大价值就是, 第i + j大的书本价格 (前面i个标签已经用过)

$f_i:=买了状态为i的书本的最大优惠$

转移:
$f_i=max(f_{i^{\wedge }j}+w[num{s}_i])$
nums_i是状态i中1的数量, 即选了这么多书

见代码2

代码

代码1

#include 
#define ll long long
#define PII pair<int, int>
#define fp(i, a, b) for (int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = (a), i##_ = (b) - 1; i > i##_; --i)
#define debug(a) cout << #a << "=" << a << endl;
#define pb push_back
#define endl '\n'
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3f 
using namespace std;
const int N = 2e6 + 10, p = 998244353;
void init_code(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	#endif
}
int w[20];
int f[1 << 16];
int main(int argc, char const *argv[])
{	
	init_code();
	
	int n, m;
	cin >> n >> m;
    memset(f, 0x3f, sizeof f);
	fp(i, 0, n - 1) {
		cin >> w[i];
        f[1 << i] = w[i];
	}
	
	fp(i, 1, m) {
		int k; 
		cin >> k;
		int sum = 0;
		int sm = INF;
		int s = 0;
		fp(j, 1, k) {
			int id; 
			cin >> id;
			s |= (1 << id - 1);
			sum += w[id - 1];
			sm = min(sm, w[id - 1]);
		}
		sum -= sm;
		f[s] = min(f[s], sum);
	}
	f[0] = 0;
	for(int i = 0; i < 1 << n ; i ++ ) {
		for(int j = i; j; j = (j - 1) & i) {
			f[i] = min(f[i], f[j] + f[j ^ i]);
		}
		
	}

	cout << f[ (1 << n) - 1];
	return 0;
}

代码2

#include 
#define ll long long
#define PII pair<int, int>
#define fp(i, a, b) for (int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = (a), i##_ = (b) - 1; i > i##_; --i)
#define debug(a) cout << #a << "=" << a << endl;
#define pb push_back
#define endl '\n'
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3f 
using namespace std;
const int N = 2e6 + 10, p = 998244353;
void init_code(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	#endif
}
int w[20];
int f[1 << 16];
int nums[1 << 16];
bool st[1 << 16];
int main(int argc, char const *argv[])
{	
	init_code();
	
	int n, m;
	cin >> n >> m;
	fp(i, 0, n - 1) {
		cin >> w[i];   
	}
    
    sort(w, w + n, greater<int>());
    	
	fp(i, 1, m) {
		int k; 
		cin >> k;
		int s = 0;
		fp(j, 1, k) {
			int id; 
			cin >> id;
			s |= (1 << id - 1);
		}   
        st[s] = 1;
        nums[s] = k; 
	}
	int sum = accumulate(w, w + n, 0);
    int ans = INF;
	for(int i = 1; i < 1 << n ; i ++ ) {
		for(int j = i; j; j = (j - 1) & i) {
            if(st[j]) {
                f[i] = max(f[i], f[i ^ j] + w[nums[i] - 1]);
            } 
		}
        ans = min(ans, sum - f[i]);
	}

	cout << ans;
	return 0;
}