矩阵消除游戏

矩阵消除游戏

https://ac.nowcoder.com/acm/problem/200190

题意:
有一个n*m的矩阵,你可以进行k回合的游戏,每一回合将矩阵的一行或者一列的值置零并将分数加上。求你最后最多能得多少分?

思路:
由于消除行对列有影响,所以不能简单的贪心,但你n和m小于15,所以我可以枚举消除列的状态,然后对每一种合理状态再对行进行贪心操作,然后取最大分数值。

代码:

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000007

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int d[20][20], n, m, rl[20], cl[20], r[20], ki;

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    scanf("%d%d%d",&n,&m,&ki);
    for(int i=0; i<n; i++)
    {
        rl[i]=0;
        for(int j=0; j<m; j++)
        {
            scanf("%d",&d[i][j]);
            rl[i]+=d[i][j];
        }
    }
    for(int j=0; j<m; j++)
    {
        cl[j]=0;
        for(int i=0; i<n; i++)
        {
            cl[j]+=d[i][j];
        }
    }
    int k=0;
    int pa=(1<<m);
    int ans=0;
    for(;k<pa;k++)
    {
        int sum=0, pan=ki;
        memset(r,0,sizeof(r));
        for(int j=0; j<m; j++)
        {
            if((k>>j)&1)
            {
                pan--;
                sum=sum+cl[j];
            }
            else
            {
                for(int i=0; i<n; i++)
                {
                    r[i]+=d[i][j];
                }
            }
        }
        if(pan<0)
        {
            continue;
        }
        sort(r,r+n,cmp);
        for(int i=0;i<pan&&i<n;i++)
        {
            sum=sum+r[i];
        }
        ans=max(sum,ans);
    }
    cout << ans << endl;
    return 0;
}
全部评论
了不起的阳阳姐
点赞 回复 分享
发布于 2020-11-19 19:35

相关推荐

06-27 15:15
长安大学 Java
哈哈哈,你是老六:这种就是培训机构骗钱的
点赞 评论 收藏
分享
大方的大熊猫准备进厂:1.教育背景:你希望从事什么专业的工作你的主修课就是什么;成绩优秀是你应该做的,没什么可描述的,成绩不优秀也许人家在大学忙着创业呢?(成绩优秀不一定是好事,只能说明多元化的大学你上成了高中,没有真正上明白大学,反而体现了你死板,不爱社交,没有别的突出能力) 2.实践经历:你想表达的意思没有说清楚。你是说你会个性化服务,还是你有实习经历。如果没有带来,经济收益,表彰,更好的发展前景,那你还不如说说提升了自己哪些技能。你说有人给你送锦旗我都能明白你优秀,但是你说你会xxxx,你说这话谁信,证据呢。 3.入伍经历:你描述的就是你的工作职责或者你应该做的,并没有体现出来你把这个事情做好了,而且入伍经历并不能证明你能干好你要应聘的工作,不如只写经历其余所有内容都不写。 4.荣誉技能:重点突出一下,但不要过多描述,这些荣誉的含金量懂得都懂。 重点:你要应聘什么工作(具体岗位,实习生不具体),你的期望薪资
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务