代码无法找到最大总和

Question

Link to CodeChef problem MAXSC

尝试的解决方案:

#include<stdio.h>

int main()
{
    long long int n, t, k, i, j, max[701], a[701][701], sum, flag;

    scanf( "%lld", &t );

    for( k = 0 ; k < t ; k++ )
    { 
        scanf( "%lld", &n );

        for( i = 1 ; i <= n ; i++ )
        {  
            for( j = 1 ; j <= n ; j++ )
            { 
                scanf( "%lld", &a[i][j] );
                if( j == 1)
                    max[i] = a[i][1];
                if( a[i][j] > max[i] )
                    max[i] = a[i][j];
            }
        }

        sum = 0, flag = 0;

        for( i = 1 ; i <= n-1 ; i++ )
        { 
            if( max[i] &lt; max[i+1])
                sum = sum + max[i];
            else
            {
                flag = 1;
                break;
            }
        }

        if(flag == 1)
            printf("-1\n");
        else
        {
            sum = sum + max[n-1];
            printf("%lld\n", sum );
        }
    }
}

计算 E1 + E2 + ... + EN 的最大可能值。如果无法选取元素 E1、E2、...、EN，则打印 -1。

约束:
代码应该选择 N 个元素，每个序列一个；让我们用 E_i 表示从序列 A_i 中选取的元素。对于每个 i (2 ≤ i ≤ N)，E_i 应严格大于 E_i-1。

这个约束是否意味着我们必须从每行中选择最大元素？

如果你看一下给出的例子:

输入示例:

1
3
1 2 3
4 5 6
7 8 9

输出:

18

说明

示例情况 1:为了最大化分数，请从第一行中选择 3 个，从第二行中选择 6 个，从第三行中选择 9 个。所得总和为 E1+E2+E3 = 3+6+9 = 18。

如果您注意到他们提到了“最大化”。

虽然我的代码找到了最大值，但它没有被接受。

Answer 1

why is this code not being accepted?

代码的逻辑有缺陷。当max[i] < max[i+1]为 false，则设置 flag = 1;而不是考虑 a[i] 中的其他元素.

Does this constraint mean we have to choose max element from each line?

没有。目标是最大总和，而不是最大值之和。

// if( max[i] < max[i+1])
if(max[i] < max[i+1])
  sum = sum + max[i];
else {
  flag = 1;
  break;
}

解决方案在于绑定(bind)其他元素。即使失败了，也许之前的选择也应该改变。可以采用递归或其他分析。我认为首先对每行数据进行排序以避免此代码占用 n*n 是有意义的运行。编写 n*n 应该很简单解决方案(尝试每种组合)。

由于这是家庭作业，请让 OP 来开发解决方案。