说明:几个细胞依次排列成一条直线。在第一单元格中,写入给定的整数ai (i=1,2,…)。、N)。我从左边的第一个单元格开始,然后向右移动;我可以选择跳入下一个单元格或下一个单元格。每次我进入一个牢房时,我都要支付ai美元,当ai是负值的时候,或者接收ai美元,当ai是非负的时候。我最多能赚多少钱?
输入: N,a1,a2,…的整数值.,aN,由空格隔开。
输出:一个整数等于想要的利润。
约束:对于每个ai,0
例如:
输入:7 2 -1 3-2 -1 6 -5
产出: 10
我已经想出了解决问题的办法,我相信这是正确的。然而,提交测试只给我5/10。
#include <stdio.h>
int main()
{
int n,array[100];
int i = 0;
int sum = 0;
scanf("%d",&n);
for(i=0;i<n;i++){
if(scanf("%d",&array[i])){}
}
for(i=0;i<n;i++)
{
if(array[i] >= 0)
{
sum += array[i];
}
else if(array[i] < 0 && array[i+1] < 0)
{
if(array[i] > array[i+1])
{
sum += array[i];
}
else if(array[i] <= array[i+1])
{
sum += array[i+1];
i++;
}
}
}
printf("%d", sum);
return 0;
}
虽然在约束范围内输入随机输入后,我似乎能够获得可靠的输出,但代码只通过了5/10测试。你能指出你注意到的代码有什么不正常之处吗?
发布于 2019-02-05 08:19:51
考虑一下
0 -1 -2 -1000 0
当i = 1
时,算法将在第25行执行分支,因此选择0 -1 -2 0单元,尽管最优解是0 -2 0。
https://stackoverflow.com/questions/54529486
复制相似问题