本文主要是介绍51NOD 1625 夹克爷发红包 (贪心+dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接 :https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1625
收藏 
关注 在公司年会上，做为互联网巨头51nod掌门人的夹克老爷当然不会放过任何发红包的机会。
现场有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 5 10 5 7 2 10 5 10 8 3 9 5 4
Output示例
78
思路: n=10 m=200 dfs 深搜 行 枚举列 (贪心) 一个选择, 一个不选择; 0 1
问题在于 改变 行数时 对列也发生影响 ;
因此 , 两个 矩阵, 一个发生改变后,一个改变前. 我们把列 每一列的 数值加起来, 此时 行数 已经通过 0 1 选择,发生改变了 ;
把列 排序 ,安装 贪心思想来 k 次 改变 保留权值 max
代码;
#include <iostream>
#include <queue>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>using namespace std;
typedef long long ll;ll maps[15][210],maps2[15][210];
ll col[1000],n,m,x,k,res;
bool vis[210];void findy(int cont)
{ll sum=0;ll rest=k-cont;memset(maps2,0,sizeof(maps2)); memset(col,0,sizeof(col));for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(vis[i]==true)maps2[i][j]=x;elsemaps2[i][j]=maps[i][j];}for(int i=0;i<m;i++){for(int j=0;j<n;j++){col[i]+=maps2[j][i];sum+=maps2[j][i];}}sort(col,col+m);for(int i=0;i<m;i++){if(rest>0){if(col[i]<n*x){sum-=col[i];sum+=n*x;rest--;}}}res=max(res,sum);return;
}void dfs(int x,int cont)
{if(cont>k) return ;if(x==n)//到底后{findy(cont);return ;}vis[x]=1;dfs(x+1,cont+1);//选vis[x]=0;dfs(x+1,cont);//不选
}
int main()
{while(cin>>n>>m>>x>>k){res=0;memset(vis,0,sizeof(vis));for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%lld",&maps[i][j]);dfs(0,0);printf("%lld\n",res);}return 0;
}
这篇关于51NOD 1625 夹克爷发红包 (贪心+dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
