选数字 (select)
Time Limit:3000ms Memory Limit:64MB 题目描述 LYK 找到了一个 n*m 的矩阵，这个矩阵上都填有一些数字，对于第 i 行第 j 列的位置上的数为 ai,j。 由于它 AK 了 noip2016 的初赛，最近显得非常无聊，便想到了一个方法自娱自乐一番。它想到的游戏是这样的： 每次选择一行或者一列， 它得到的快乐值将会是这一行或者一列的数字之和。之后它将该行或者该列上的数字都减去 p（之后可能变成负数） 。如此，重复 k次，它得到的快乐值之和将会是它 NOIP2016 复赛比赛时的 RP 值。LYK 当然想让它的 RP 值尽可能高，于是它来求助于你。 输入格式(select.in) 第一行 4 个数 n,m,k,p。接下来 n 行 m 列，表示 ai,j。 输出格式(select.out) 输出一行表示最大 RP 值。 输入样例 2 2 5 21 32 4 输出样例 11 数据范围 总共 10 组数据。对于第 1,2 组数据 n,m,k<=5。对于第 3 组数据 k=1。对于第 4 组数据 p=0。对于第 5,6 组数据 n=1，m,k<=1000。对于第 7,8 组数据 n=1，m<=1000，k<=1000000。对于所有数据 1<=n,m<=1000，k<=1000000，1<=ai,j<=1000，0<=p<=100。 样例解释 第一次选择第二列，第二次选择第二行，第三次选择第一行，第四次选择第二行，第五次选择第一行，快乐值为 7+4+2+0+-2=11。
思路：
每次选数都会减去一些值
所以有些人可能会想记录所有的状态然来搜索
但是
仔细思考一下会发现
横行和列行每次选的值都是互不相干的
但是每次的值都是不同的
所以我们要贪心得出1到k次横行和列航的最大值
然后枚举每种情况取最优值
来，上代码：
#include#include #include #include #define big 1000000000000000using namespace std;long long int n,m,k,p,cur,s1[1002],s2[1002],jkl;long long int num1=0,num2=0,sumh[1000002],suml[1000002];long long int ans;char ch;priority_queue ha;priority_queue li;void qread(long long int &x){ x=0,jkl=1;ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') jkl=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+(long long int)(ch-'0');ch=getchar();} x*=jkl;}int main(){ qread(n),qread(m),qread(k),qread(p); ans=-big; for(long long int i=1;i<=n;i++) { for(long long int j=1;j<=m;j++) { qread(cur); s1[i]+=cur; s2[j]+=cur; } } if(p==0) { for(long long int i=1;i<=n;i++) ans=max(ans,s1[i]*k); for(long long int i=1;i<=m;i++) ans=max(ans,s2[i]*k); cout< <