首页 > 代码库 > Codeforces Round #FF/#255 D DZY Loves Modification --贪心+优先队列
Codeforces Round #FF/#255 D DZY Loves Modification --贪心+优先队列
题意：给你一个矩阵，每次选某一行或者某一列，得到的价值为那一行或列的和，然后该行每个元素减去p。问连续取k次能得到的最大总价值为多少。
解法：
如果p=0，即永远不减数，那么最优肯定是取每行或每列那个最大的取k次，所以最优解由此推出。
如果不管p，先拿，最后再减去那些行列交叉点，因为每个点的值只能取一次，而交叉点的值被加了两次，所以要减掉1次，如果取行A次，取列B次，那么最后答案为：
res = dp1[A] + dp2[B] - B*(k-A)*p，可以细细体会一下后面那部分。
其中：
dp1[A]表示在行中取A次得到的最大和（取完要减去p哦）
dp2[B]表示在列中取B次得到的最大和（~）
每次取最大的可以用优先队列来实现，思想就是这么个思想。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <queue>#define lll __int64using namespace std;#define N 1007#define M 33lll dp1[N*N],dp2[N*N];lll RS[N],CS[N];lll a[N][N];priority_queue<lll> que;int main(){ int n,m,k,p; int i,j; while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF) { memset(RS,0,sizeof(RS)); memset(CS,0,sizeof(CS)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%I64d",&a[i][j]); RS[i] += a[i][j]; CS[j] += a[i][j]; } } dp1[0] = dp2[0] = 0; while(!que.empty()) que.pop(); for(i=1;i<=n;i++) que.push(RS[i]); for(i=1;i<=k;i++) { lll tmp = que.top(); que.pop(); dp1[i] = dp1[i-1]+tmp; tmp -= (lll)m*p; que.push(tmp); } while(!que.empty()) que.pop(); for(i=1;i<=m;i++) que.push(CS[i]); for(i=1;i<=k;i++) { lll tmp = que.top(); que.pop(); dp2[i] = dp2[i-1]+tmp; tmp -= (lll)n*p; que.push(tmp); } ll res = dp1[0]+dp2[k]; for(i=1;i<=k;i++) { ll tmp = dp1[i]+dp2[k-i]-1LL*i*(k-i)*p; res = max(res,tmp); } printf("%I64d\n",res); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。