这题测试数据感觉不太严谨,这是第二次做感觉做过,就来翻了翻以前的代码
#include "cstdio" #include "cstring" #include "algorithm" #define ll long long const int maxn = 200; int maze[maxn][maxn]; int n,m,k; struct node{ int id,val; bool operator < (const node &o)const { return val>o.val; } node() { id=0; val=0; } }; node row[maxn],col[maxn]; bool cmp(const int &o,const int &v) { return o>v; } int main() { //ll n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { row[i].id=i; int x; scanf("%d",&x); row[i].val+=x; col[j].val+=x; maze[i][j]=x; } } int ans=0; int c[200]; std::sort(row+1,row+1+n); // std::sort(col+1,col+1+n); for(int i=0;i<=k;i++) { memset(c,0,sizeof(c)); int tmp=0; for(int j=1;j<=i;j++) { for(int k=1;k<=m;k++) c[k]+=maze[row[j].id][k]; tmp+=row[j].val; } for(int j=1;j<=m;j++) { c[j]=col[j].val-c[j]; } std::sort(c+1,c+1+m,cmp); for(int j=1;j<=k-i;j++) tmp+=c[j]; ans=std::max(tmp,ans); } printf("%d\n",ans); }
思路是把枚举i个行和k-i个列的消除,先消除最大的行,然后列中减去排序再找k-i个最大的列,发现有逻辑错误,应该把所有行都枚举才对,但是以前提交却ac了。。。数据问题。。
自己hack一下自己。。。
3 3 2
104 1 102
0 202 0
100 8 100
正确答案应该是417,代码跑出来415,提交ac。。。
104 1 102
0 202 0
100 8 100
正确答案应该是417,代码跑出来415,提交ac。。。
全部评论
(0) 回帖