自动搬运

查看原文

来自洛谷，原作者为

	JK_LOVER 却顾所来径，苍苍横翠微。

搬运于2025-08-24 22:04:49，当前版本为作者最后更新于2020-08-24 19:03:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给你一个 $n\times n$ 大小的矩阵，每一行和每一列都只能选取 $1$ 个点，每个点都有 $val_{i,j}$ 的收益。当在某行取了之后，如果不小于一些值，还可以多获得 $A_i$ 的收益。$QWQ$

分析

读完题，可以发现一个很好的性质，$i,j$ 是唯一对应的。那么可以考虑 $dp$ ，定义状态 $dp[s]$ 表示选取了 $s$ 这个集合之后的最大收益。那么就有如下转移

那么考虑额外贡献，因为可以自己安排顺序，那么一定要让 $P_i$ 最小的靠前。这个很容易想到。那么总复杂度为 $O(n\times 2^n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 21;
struct ex{
	int P,A;
};
vector<ex> e[N];
bool cmp(ex a,ex b) {return a.P < b.P;}
int dp[(1<<N)+10],val[N][N],n,m;
int main()
{
	n = read();m = read();
	for(int i = 1;i <= m;i++) {
		int a = read(),b = read(),c = read();
		e[a].push_back((ex){b,c});
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) {
			val[j][i] = read();
		}
	}
	for(int i = 1;i <= n;i++) sort(e[i].begin(),e[i].end(),cmp);
	for(int s = 1;s < (1<<n);s++){
		int S = 0;
		for(int j = 1;j <= n;j++) S += ((s>>(j-1))&1);
//		cout << S << " " << s << endl;
		for(int j = 1;j <= n;j++) {
			if((s&(1<<j-1))) {
				dp[s] = max(dp[s],val[S][j]+dp[s^(1<<j-1)]);
			}
		}
		for(int j = 0;j < e[S].size();j++){
			if(dp[s] >= e[S][j].P) dp[s] += e[S][j].A;
		}
	}
	printf("%d\n",dp[(1<<n)-1]);
	return 0;
}