杀怪物（暴力）

题目描述

为了庆祝自己的生日，小张推出一款游戏。游戏在一个20*20的方格上进行，上面有一些怪物，用#表示，其他是空格，用 . 表示。怪物有两点体力。体力为0时死亡。

你可以进行以下操作：

（1）使一个横行上的怪物体力减一

（2）使一个竖行上的怪物体力减一

对每个横行或竖行只能操作一次，限定n次，问最多能杀死多少个怪物。

输入

第一行为整数n（1≦n≦40），表示操作的次数。

接下来是一个20*20的方格，#表示怪物，.表示空格。

格式参考输入样例。

输出

输出最多能杀死的怪物数量。

样例输入

【样例1】

3

…

…

…###…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

【样例2】

10

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

样例输出

【样例1】

2

【样例2】

25

思路

暴力求解即可

代码实现

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=55;
const int M=20;
const int INF=0x3f3f3f;
const ull sed=31;
const ll mod=1e9+7;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef pair<int,int>P;
 
int n,ans;
char mp[N][N];
int h[N],vis[N];
 
void dfs(int p,int cnt)
{
    if(cnt>=n) return ;
    int op=n-cnt,ret=0;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=M;i++) vis[h[i]]++;
    for(int j=M;j && op;j--)
    {
        if(vis[j]<=op)
        {
            ret+=vis[j]*j;
            op-=vis[j];
        }
        else
        {
            ret+=op*j;
            op=0;
        }
    }
    ans=max(ans,ret);
    for(int i=p;i<=M;i++)
    {
        for(int j=1;j<=M;j++) if(mp[i][j]=='#') h[j]++;
        dfs(i+1,cnt+1);
        for(int j=1;j<=M;j++) if(mp[i][j]=='#') h[j]--;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=M;i++) scanf("%s",mp[i]+1);
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}