题解 P4877 【[USACO14FEB]Cow Decathlon G】

· · 题解

题意

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

分析

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

dp[s] = \max(dp[s-j] + val[count(s)][j]) \ j\in 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;
}