锯齿形序列[动态规划]错误

我目前正在学习DP和我通过topsider教程学习，并试图解决的问题和了解，并知道解决办法是非常相似的计算长度去最长增加子序列。我编程的简单的C++ DP的解决方案如下：锯齿形序列[动态规划]错误

#include <iostream> 
#include <vector> 
using namespace std; 

int main(void) 
{ 
    int n = 50; 
    int numbers[] =   
{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }; 
    vector<int> length(n, 1); 
    for(int i = 1;i < n;i++) 
    { 
     for(int j = (i - 1);j >= 0;j--) 
     { 
      if(length[j] + 1 > length[i]) 
      { 
       if(length[j] % 2 == 0) 
       { 
        if(numbers[i] - numbers[j] < 0) 
        { 
         length[i] = length[j] + 1; 
        } 
       } 
       else 
       { 
        if(numbers[i] - numbers[j] > 0) 
        { 
         length[i] = length[j] + 1; 
        } 
       } 
      } 
     } 
    } 
    printf("%d\n", *(max_element(length.begin(), length.end()))); 
}

但问题是代码正常工作对所有其他情况下，除了这一个：

{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

我的代码打印答案35而topsider相信它的36。我知道我在程序中犯了一些愚蠢的错误，但一段时间以来一直试图找到它，其他人能帮我找出错误吗？

来源

2015-01-06 Nalin Bhardwaj

程序中最大的问题是它没有评论。这对于编程竞赛来说很好，但是当你把它提交给像这样的论坛寻求帮助和建议时不会。 – TonyK

@TonyK Ya，我知道，这是我最大的弱点之一，非常抱歉，我的竞争意识非常强烈，但我有时觉得在代码中添加注释会破坏工作流程，有时会导致代码混乱......此外，我正在为INOI准备这些天，因此我的工作重点完全在于algorirhms，而不是代码之美。 –

我怀疑的问题是，第一差可以是正的或负的，但你的代码只支持其中一个案件。

也许你应该积极的，然后再第二次负第一两次运行此代码，一次。

来源

2015-01-06 18:34:09

嗯，错误地假设了...... :) –

锯齿形序列[动态规划]错误

回答

相关问题