[問題] ACM497還是有點點問題

[SPower (xx)]

感謝khoguan 還有cplusplsu兄的指點
不過還是吃了WA >< 不知道可以幫我看看那裡有問題 thanks
以下是題目網址
http://www2.dmhs.kh.edu.tw/homework/q497.htm

我先簡述一下我的作法
假設輸入 資料 suit[9] ={1,3,5,7,8,2,9,10,6}
程式中//compute部份先求得 該元素
longest[i] 代表
"the length of the longest increasing subsequence ending with the index i"

所以得到longest[9]={1,2,3,4,5,2,6,7,4}
best = 7
然後scan longest array  from left to right
若longest[i] 的值 和其右邊longest[i+1] 差1的話就輸出 suit[i]
所以輸出 1 3 5 7 8 9 10
作法大概是降子
以下是程式碼

#define N 2000
using namespace std;
inline int max(int ,int );

int main(int argc, char *argv[])
{
        int suit[N];
        int num;
        string line;

        cin>>num;
        getline(cin,line);
        getline(cin,line);

        int count=0;                   //紀錄單一sequence的data個數
        while(num) {
                while(1)
                {
                        getline(cin,line);
                        if(line.length()==0)        // newline 結束
                                break;
                        suit[count++] = atoi(line.c_str());

                }
                //compute
                int longest[N];
                for (int i = 0; i < count; i++) {
                    longest[i] = 1;
                    for (int j = i-1; j >= 0; j--) {
                         if (suit[j] <= suit[i])
                             longest[i] = max(longest[i], 1 + longest[j]);
                    }
                }

                int best = 0;
                for (int i = 0; i < count; i++) best = max(best, longest[i]);

                //find first number from 1 become 2
                int i;
                for(i=0;longest[i]!=2;i++)
                        ;
                i--;
                cout<<endl<<"Max hits: "<<best<<endl<<suit[i]<<endl;
                int temp=i+1;
                for(;longest[temp]!=best;temp++)
                {
                        if(longest[temp]==longest[i]+1) {
                                cout<<suit[temp]<<endl;
                                i = temp;
                        }
                }
                cout<<suit[temp]<<endl;
                --num;                        //繼續處理下一筆資料
                if(num!=0) cout<<endl;        //最後一筆output不用換行
                count=0;
        }
        return 0;
}

inline int max(int a,int b)
{
        if(a>b)
                return a;
        else
                return b;
}

--
感謝了~

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.163.135.54
※ 編輯: SPower          來自: 218.163.135.54       (06/15 23:42)
→ SPower:恩 剛剛找到一個問題 沒處理null的情形..@@
推 windows2k:cplusplus :D
推 cplusplus:windows2k :p
推 SPower:我想請問一下 沒有飛彈要中止還是當作是0然後輸出
推 khoguan:要輸出哦 Max hits: 0
> -------------------------------------------------------------------------- <

作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] ACM497還是有點點問題
時間: Thu Jun 16 16:40:35 2005

※ 引述《SPower (xx)》之銘言：
: 感謝khoguan 還有cplusplsu兄的指點
: 不過還是吃了WA >< 不知道可以幫我看看那裡有問題 thanks
: 以下是題目網址
: http://www2.dmhs.kh.edu.tw/homework/q497.htm
: 我先簡述一下我的作法
: 假設輸入 資料 suit[9] ={1,3,5,7,8,2,9,10,6}
: 程式中//compute部份先求得 該元素
: longest[i] 代表
: "the length of the longest increasing subsequence ending with the index i"
: 所以得到longest[9]={1,2,3,4,5,2,6,7,4}
: best = 7
: 然後scan longest array  from left to right
: 若longest[i] 的值 和其右邊longest[i+1] 差1的話就輸出 suit[i]

  這個不太對。試處理這份測資：

1

1
6
2
3
5

  你的程式會跑出 1 6 3 5 的不正確結果。

  要再多弄個陣列，放 predecessor, 也就是走到每個點的上一個點的位置。
  然後從 longest[i] 最大的那個位置，一步一步走回去到第一個(不一定是
  輸入資料的第一個哦)，邊走邊將 target值 push 到 stack, 然後再 pop
  印出來（另用陣列倒著印也成)。

  這是我的做法，應該還有更聰明的解法，還請板上的大大們指教。

  提供一個很不錯網址：
http://www.comp.nus.edu.sg/~stevenha/programming/
prog_dynamicprogramming.html#5._Longest_Inc/Dec-reasing_Subsequence_(LIS/LDS)

: 所以輸出 1 3 5 7 8 9 10
: 作法大概是降子

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.130.208.166