洛谷 P2356 【弹珠游戏】题解

自我感觉应该没有用结构体做的吧

这道题其实非常水

很适合初学贪心的同学做一下

我好像没有用贪心做，嘻嘻

首先先读题，

题目中说这个游戏只能消灭当前所在位置的行、列的敌人

首先特判一下：

if(tt==1)
{
cout<<"Bad Game!"<<endl;
return 0;
}

这个里面的tt指的是有没有落脚点，但是我为了好存结构体

所以我一开始初始化的值为一

然后就特判是否为一，也就是有没有落脚点

然后开始挨个从能落脚的地方枚举：

for(int i=1;i<=tt;i++)
{
int sum1=0;
for(int j=1;j<=n;j++)
{
sum1+=map[j][zuo[i].y];
}
for(int j=1;j<=n;j++)
{
sum1+=map[zuo[i].x][j];
}
maxn=max(maxn,sum1);
}

第一层是枚举所有的落脚点

第二层是枚举当前落脚点所在的行，列的值，然后加起来

最后比较一下，选出最大值，再输出就好了

完整代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>using namespace std;int map[1010][1010];
struct node
{
int x;
int y;
}zuo[10001];int main()
{
int n;
cin>>n;
int tt=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>map[i][j];
if(map[i][j]==0)
{
zuo[tt].x=i;
zuo[tt].y=j;
tt++;
}
}
}
int maxn=0;
if(tt==1)
{
cout<<"Bad Game!"<<endl;
return 0;
}
else
{
for(int i=1;i<=tt;i++)
{
int sum1=0;
for(int j=1;j<=n;j++)
{
sum1+=map[j][zuo[i].y];
}
for(int j=1;j<=n;j++)
{
sum1+=map[zuo[i].x][j];
}
maxn=max(maxn,sum1);
}
}
cout<<maxn<<endl;
return 0;
}