求救

我使用二维向量,并多出一行一列来存放每行每列的和,操作一次就更新权值和每行每列的和,但是通过95,请大佬看看我是少考虑什么了吗?不胜感激

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    int i=0,j=0;
 int score=0;
    vector<vector<int> > vec(n+1,vector<int>(m+1));
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            cin>>vec[i][j];
        }
    }
 while(k!=0)
 {
  for(i=0;i<n;i++)
   for(j=0;j<m;j++)
    vec[i][m]+=vec[i][j];
  for(j=0;j<m;j++)
   for(i=0;i<n;i++)
    vec[n][j]+=vec[i][j];
  int score_raw=0;
  int raw=0;
  int score_col=0;
  int col=0;
  for(i=0;i<n;i++)
  {
   if(vec[i][m]>score_raw)
   {
    score_raw=vec[i][m];
    raw=i;
   }
  }
  for(j=0;j<m;j++)
  {
   if(vec[n][j]>score_col)
   {
    score_col=vec[n][j];
    col=j;
   }
  }
  if(score_raw>score_col)
  {
   score+=score_raw;
   for(j=0;j<m;j++)
   {
    vec[raw][j]=0;
   }
  }
  else
  {
   score+=score_col;
   for(i=0;i<n;i++)
   {
    vec[i][col]=0;
   }
  }
  for(i=0;i<n;i++)
   for(j=0;j<m;j++)
    vec[i][m]=0;
  for(j=0;j<m;j++)
   for(i=0;i<n;i++)
    vec[n][j]=0;
  k--;
 } 
 cout<<score;
    return 0;
}
全部评论
建议你去看下别人的题解,这个不是一次一次操作出来的,是要把所有可能的情况都放在一起比较的。 不是每次操作我记录下来再找下一个数值最大的行或列就行的。 😶下面引用题解作者  荷塘涟漪  的原文: 如果我每次贪心的选剩下的图中最大的一行或者一列,然后把这一行(列)抹为0可以吗?(既按照题目描述步骤每一步贪心,这样的局部最优解能得到全局最优解吗?)     我想这又是一个可能会坑到的地方。     先也给一组反例:     4 4 3     1 1 9 3     1 8 10 8     1 2 7 2     1 2 2 2     一步一步贪心话先选第三列,第三列清零;然后选第二行,最后选第四列。但是选第二三四列更好哇。
点赞
送花
回复
分享
发布于 2020-03-02 23:51

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务