AT_abc018_4 题解

· · 题解

题目传送门

思路

本题使用 dfs。

首先用类似邻接矩阵的方式存储幸福值，即 A_{{X_i},{Y_i}}=Z_i。

然后遍历老师。对于老师，每一个老师有选与不选两种情况，需要做 dfs。做完 N 次遍历后，我们得到了一个表 V，其中 V_i 代表第 i 名老师是否参加活动。

随后处理学生。对于所有的学生，对于参加的老师和学生统计出幸福值总数。将得到的序列降序排序，取前 Q 的和与答案取最大值。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=20;
int n,m,e,q,ans,a[N][N],p[N];
bool vis[N];
void dfs(int x,int y){
    if(y>e)
        return;
    if(x>n){
        if(y==e){
            memset(p,0,sizeof(p));
            for(int i=1;i<=n;++i)
                for(int j=1;j<=m;++j)
                    p[j]+=vis[i]*a[i][j];
            sort(p+1,p+m+1,greater<int>());
            int sum=0;
            for(int i=1;i<=q;++i)
                sum+=p[i];
            ans=max(ans,sum);
        }
        return;
    }
    vis[x]=true,dfs(x+1,y+1);
    vis[x]=false,dfs(x+1,y);
    return;
}
int main(){
    n=read(),m=read(),e=read(),q=read();
    int r=read();
    while(r--){
        int x=read(),y=read(),z=read();
        a[x][y]+=z;
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}