ZOJ1025-Wooden Sticks 加工木棒問題

【問題描述】

現(xiàn)有n根木棒，已知它們的長度和重量。要用一部木工機(jī)一根一根地加工這些木棒。該機(jī)器在加工過程中需要一定的準(zhǔn)備時間用于清洗機(jī)器、調(diào)整工具和模板。

木工機(jī)需要的準(zhǔn)備時間如下：

（1）   第一根木棒需要1min的準(zhǔn)備時間；

（2）   在加工了一根長為l，重為w的木棒后，接著加工一根長為l’(l≤l’)，

重為w’(w≤w’)的木棒是不需要任何準(zhǔn)備時間的，否則需要1min的準(zhǔn)備時間。

給定n根木棒，你要找到最少的準(zhǔn)備時間。例如現(xiàn)在有長度和重量分別為（4,9）、（5,2）、（2,1）、（3,5）和（1,4）的5根木棒，那么所需準(zhǔn)備時間最少為2min，順序為（1,4）-》（3,5）-》（4,9）-》（2,1）-》（5,2）。

【輸入】

輸入有多組測試?yán)?。輸入?shù)據(jù)的第一行是測試?yán)膫€數(shù)T。

每個測試?yán)齼尚校?/p>

第一行是一個整數(shù)n（1≤n≤5000），表示有多少根木棒；

第二行包括n×2個整數(shù)，表示l1,w1,l2,w2,l3,w3,…,ln,wn，全部不大于10000，其中l(wèi)i和wi表示第i根木棒的長度和重量。

數(shù)據(jù)由一個或多個空格分隔。

【輸出】

輸出是以分鐘為單位的最少準(zhǔn)備時間，一行對應(yīng)一個測試?yán)?/p>

【輸入樣例】                                       

3                                                  

5                                                  

4 9 5 2 2 1 3 5 1 4                                

3

2 2 1 1 2 2

3

1 3 2 2 3 1

【輸出樣例】

2

1

3

思路：

拿分析的樣例來看，直接想到了離散上的偏序集，但只是想到了，不知道該怎么解。。。

看了下題解有了思路。先通過一輪cmp構(gòu)造的排序，將問題進(jìn)行轉(zhuǎn)化——按照每個棒子的長度從小到大進(jìn)行排序，然后得到基于棒子長度從小到大排序的棒子重量數(shù)組，將這個數(shù)組提取到w中保存，或者你不提出來也行，我就是為了方便，我稱之為空間換簡潔。

然后我們在把2維的偏序關(guān)系降到1維后（對，這個題就是降維打擊：），就發(fā)現(xiàn)現(xiàn)在問題已經(jīng)轉(zhuǎn)換成了求w數(shù)組的最長上升子序列的最小個數(shù)，而這個問題，可以再次轉(zhuǎn)換成求w數(shù)組的最長遞減子序列的長度。后者的轉(zhuǎn)換很容易理解，比如這個數(shù)組w的最長遞減子序列的長度為5，那這5個值肯定各自在一個獨(dú)立的最長上升子序列中。

兩行大概就把問題的核心說清了，然后coding

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 5007
using namespace std;

int n,T;
struct stick{
    int l,w;
} sticks[N];
int w[N];
int dp[N];

bool cmp(stick a,stick b)
{
    if(a.l == b.l)
        return a.w < b.w;
    else if(a.l < b.l)
        return true;
    return false;
}

int LIS(int* w)
{
    int j;//j為當(dāng)前最大結(jié)束點(diǎn)的坐標(biāo) 
    dp[j=1] = w[1];
    for(int i = 2;i <= n;i++)
    {
        if(w[i] < dp[j]) 
            dp[++j] = w[i];
        else if(w[i] == dp[j]) continue;
        else {
            for(int k = j;k >= 1;k--)
            {
                if(k == 1) 
                    dp[1] = w[i]>dp[1]?w[i]:dp[1];
                //找到所有“合適”的位置 
                if(w[i]>dp[k] && w[i]<dp[k-1]) 
                    dp[k] = w[i];
            }
        }
    }
    return j;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        int ans = 0;
        for(int i = 1;i <= n;i++)
            cin>>sticks[i].l>>sticks[i].w;
        sort(sticks+1,sticks+1+n,cmp);
        for(int i = 1;i <= n;i++) 
            w[i] = sticks[i].w;
        cout<<LIS(w)<<endl;
    }
    return 0;
}