当前位置 : 主页 > 编程语言 > c语言 >

1625 夹克爷发红包,暴力+贪心

来源:互联网 收集:自由互联 发布时间:2023-09-03
1625夹克爷发红包 基准时间限制:1秒 空间限制:131072KB 分值:20 难度:3级算法题 现场有n排m列观众,夹克老爷会为每一名观众送出普通现金红包,每个红包内金额随机。 接下来,夹克老





1625 夹克爷发红包



基准时间限制:1 秒 空间限制:131072 KB 分值: 20  难度:3级算法题





现场有n排m列观众,夹克老爷会为每一名观众送出普通现金红包,每个红包内金额随机。



接下来,夹克老爷又送出 最多k组高级红包,每 组高级红包会同时给一排或一列的人派发 ,每 个高级红包的金额皆为x。



派发高级红包时,普通红包将会强制收回。同时,每个人只能得到一个高级红包。(好小气!)



现在求一种派发高级红包的策略,使得现场观众获得的红包总金额最大。


Input


第一行为n, m, x, k四个整数。1 <= n <= 10, 1 <= m <= 200 1 <= x <= 10^9,0 <= k <= n + m 接下来为一个n * m的矩阵,代表每个观众获得的普通红包的金额。普通红包的金额取值范围为1 <= y <= 10^9


Output


输出一个整数,代表现场观众能获得的最大红包总金额


Input示例


3 4 1 510 5 7 2 10 5 10 8 3 9 5 4


Output示例


78



分析:

原本想 每次找到一行或者一列得到钱数最多,把这一行给更新就行

wrong到无法自拔之后,决定暴力吧,数据还不算大


这里我用的BFS广搜,同时优先队列优化(自我感觉普通队列也无妨,不过超内存了)


这里,我用结构体存矩阵(幸亏数据不大,内存没超)

队列的每个元素也是一个结构体矩阵

结构体内同时存储行之和,列之和,总和。还有一个记步变量step


数据输入时,不采用存原数据,而是存每一个数和x的差值,

这样就把矩阵所有数据降低了x,所以可以看做老爷子发的高级红包都是0元

如此一来,我们只需要致力于 把达不到0的数尽力刷成0;

最后再用n*m*x加上矩阵总和,即为答案


BFS时的每一步,都找一个最小行(和最小)最小列,

如果这一行或列小于0(即达不到0),可以被刷新,再装进队列


相当于遍历所有的可能的最优情况

另外,用BFS+优先队列+结构体矩阵 解这个题不太好,内存和时间不敢保证

DFS解决会更好些



#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
struct arr{
	ll a[11][201];
	ll r[11];//行和
	ll c[201];//列和
	ll sum;
	int step;
	friend bool operator < (arr n1,arr n2)
	{
		return n1.sum<n2.sum;//优先队列先出大的
	}
};
ll m,n,x,k;
priority_queue<arr> q;
int find(ll r[],int nn)//找最小行(或列)   
{
	ll min=r[1];
	int k=1;
	for(int i=2;i<=nn;i++)
	{
		if(min>r[i])
		{
			k=i;
			min=r[i];
		}
	}
	return k;//最小行(或列)的行号(列号) 
}
void replace_r(arr &t,int mm,int ki)//修改行 
{
	t.r[ki]=0;
	for(int j=1;j<=mm;j++)
	{
		t.sum-=t.a[ki][j];
		t.c[j]-=t.a[ki][j];
		t.a[ki][j]=0;
	}
}
void replace_c(arr &t,int nn,int kj)//改列
{
	t.c[kj]=0;
	for(int i=1;i<=nn;i++)
	{
		t.sum-=t.a[i][kj];
		t.r[i]-=t.a[i][kj];
		t.a[i][kj]=0;
	}
}
ll BFS()
{
	ll ans=-1111111111122111;
	while(!q.empty())
	{
		arr t=q.top();
		q.pop();
		if(t.step>k)//步数超过k,不必再下去 
			continue;
		if(ans<t.sum)//更新最大answer 
			ans=t.sum;
		int ki=find(t.r,n);//最小行
		int kj=find(t.c,m);//最小列
		arr t1;
		memcpy(&t1,&t,sizeof(t));//复制出一个t1,以便入队列 
		if(t1.r[ki]<0)
		{
			replace_r(t1,m,ki);//清行
			t1.step++;//入队列前步数+1 
			q.push(t1);
		}
		if(t.c[kj]<0)
		{
			replace_c(t,n,kj);//清列
			t.step++;
			q.push(t);
		}
	}
	return  n*m*x + ans;
}
int main()
{
	arr t;
	while(scanf("%lld%lld%lld%lld",&n,&m,&x,&k)!=EOF)
	{
		memset(&t,0,sizeof(t));//把t内数据全部清0
		while(!q.empty()) q.pop();//保证队列是空的 
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				ll d;
				scanf("%lld",&d);
				t.a[i][j]=d-x;//矩阵存d与x的差距
				t.c[j]+=d-x;//c存每一列的总和 
				t.r[i]+=d-x;//r存每一行的总和 
				t.sum+=d-x;//存矩阵总和 
			}
		}
		q.push(t);
		printf("%lld\n",BFS());
	}
	return 0;
 }




上一篇:C++练手小项目:职工工资信息管理系统
下一篇:没有了
网友评论