欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  web前端

codeforces#FF(div2) D DZY Loves Modification_html/css_WEB-ITnose

程序员文章站 2022-05-19 12:18:31
...
首先要知道选择行列操作时顺序是无关的

用两个数组row[i],col[j]分别表示仅选择i行能得到的最大值和仅选择j列能得到的最大值

这个用优先队列维护，没选择一行(列)后将这行(列)的和减去相应的np (mp)重新加入队列


枚举选择行的次数为i,那么选择列的次数为k - i次，ans = row[i] + col[k - i] - (k - i) * i * p;

既然顺序无关，可以看做先选择完i次行，那么每次选择一列时都要减去i * p，选择k - i次列，即减去(k - i) * i * p


//#pragma comment(linker, "/STACK:102400000,102400000")//HEAD#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//LOOP#define FE(i, a, b) for(int i = (a); i = (a); --i)#define REP(i, N) for(int i = 0; i = (a); --i)#define CPY(a, b) memcpy(a, b, sizeof(a))#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)#define EQ(a, b) (fabs((a) - (b))  VI;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const int maxn = 1010;const double eps = 1e-10;const LL MOD = 1e9 + 7;int ipt[maxn][maxn];LL row[maxn * maxn], col[maxn * maxn];LL rtol[maxn], ctol[maxn];int main(){    int n, m, k, p;    while (~RIV(n, m, k, p))    {        priority_queue r, c;        int radd = 0, cadd = 0;        CLR(rtol, 0), CLR(ctol, 0);        FE(i, 1, n)            FE(j, 1, m)            {                RI(ipt[i][j]);                rtol[i] += ipt[i][j];                ctol[j] += ipt[i][j];            }        FE(i, 1, n)            r.push(rtol[i]);        FE(j, 1, m)            c.push(ctol[j]);        row[0] = 0, col[0] = 0;        FE(i, 1, k)        {            LL x = r.top(), y = c.top();             r.pop(), c.pop();            r.push(x - m * p);            c.push(y - n * p);            row[i] = row[i - 1] + x;            col[i] = col[i - 1] + y;        }//        FE(i, 0, k)//            cout
相关标签： loves div2 dzy codeforces#ff modification

上一篇： php学习笔记8--半边引号引发的问题，学习笔记8--半边引号_PHP教程

下一篇： 烂泥：通过binlog恢复mysql数据库

推荐阅读