AT_abc018_4 [ABC018D] バレンタインデー 题解

· · 题解

思路：

首先看到部分分，n\leq8 且 m\leq8。对于这个数据范围，显然枚举学生集合和老师集合，最后算贡献即可。满分的数据范围，n\leq18 且 m\leq18，这个数据范围启示我们省略冗余的枚举。考虑只枚举老师集合，对于学生集合，由于学生人数和老师人数无关，也就是说老师的选择对学生的选择没有影响，所以直接贪心选几个加进来能使贡献最大的就行了。

Code：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int res=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
    return res*f;
}
void write(int x)
{
    if(x<0){x=-x;putchar('-');}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,m,p,q,k;
int w[1145][1145];
int t[114514],cnt,s[114514];
int ans;
void dfs(int step)
{
    if(step>n)
    {
        if(p<cnt)
            return;
        int res=0;
        memset(s,0,sizeof s);       
        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=m;j++)
                s[j]+=w[t[i]][j];
        sort(s+1,s+m+1);
        for(int i=m;i>max(0,m-q);i--)
            res+=s[i];
        ans=max(ans,res);
        return;
    }
    t[++cnt]=step;
    dfs(step+1);
    --cnt;
    dfs(step+1);
}
int main()
{
    n=read(),m=read(),p=read(),q=read(),k=read();
    for(int i=1;i<=k;i++)
    {
        int x=read(),y=read(),z=read();
        w[x][y]=z;
    }
    dfs(1);
    write(ans),puts("");
}