1625 夹克爷发红包 基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题 在公司年会上，做为互联网巨头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
#include<stdio.h>//发红包的那个，思路是先对行用dfs选或不选，剩下的高级红包组数分到列里， //之后再计算列的钱数，从小到大排序，选最小的几个如果最小的几个替换成x之后 比之前的总钱数多则替换否则不替换。 #include<string.h> #include<algorithm> using namespace std; long long n,m,x,k,ans=0; long long count0[205]; long long a[15][205],b[15][205];//b[][]用来记住替换后的数组； int vis[15]; void select(int t){ int i,j; long long sum=0; int d; d=k-t; for(i=1;i<=n;i++){ if(vis[i]==1) for(j=1;j<=m;j++) b[i][j]=x; else for(j=1;j<=m;j++) b[i][j]=a[i][j]; } memset(count0,0,sizeof(count0)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) count0[j]+=b[i][j];//计算每一列的总钱数 sort(count0+1,count0+m+1); for(i=1;i<=m;i++){ if(d>0){ if(count0[i]<n*x) sum+=(n*x); else sum+=count0[i]; d--; } else sum+=count0[i]; } ans=max(ans,sum); } void dfs(int t,int deep){ if(deep>n){ select(t); return ; } if(t>k) return ; vis[deep]=1; dfs(t+1,deep+1); vis[deep]=0; dfs(t,deep+1); } int main() { int i,j; while(~scanf("%d%d%d%d",&n,&m,&x,&k)){ for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); memset(vis,0,sizeof(vis)); dfs(0,1); printf("%lld\n",ans); } return 0; }
