UVa12385 - Interesting Sequences (水題)

題目大意：

給你一個數列，請找出 「Interesting Sequences」共有幾組。

分析：

唉，看來我的英文能力需要增加。

「Interesting Sequences」 定義如下:

1. 在 Interesting Sequences 中頭尾數字一樣
2. 不是每個 Interesting Sequences 的數字都要一樣

ex1: 4 2 3 5 9 2 1

1. 2 3 5 9 2

ex2: 3 2 3 1 3 2 3 2 2 2 2

1. 2 3 1 3 2
2. 2 2 index: 8 9
3. 2 2 index: 9 10
4. 2 2 index: 10 11

就這麼簡單，用「動態規劃」解決這題即可

DP規則如下( 透過 greedy 優化 )：

1. 透過陣列記住每個數字最後的位置
2. last 做為上次 Interesting Sequences 的最後 index，因為 Interesting Sequences 不可以重疊。
3. 如果 數字最後的位置 >= last , ans +=1

題外話:

這題幾乎沒什麼人寫過，資源量好少，然後英文真的是不太好理解阿，花了 2、3 天才理解這題題意是甚麼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin);
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL

    int n ,t , last , ans , temp ;
    int num[100020] = {} ;
    cin >> t ;
    while(t--){
        ans = 0;
        last = 0 ;
        for(int i = 0 ; i < 100020 ; i++)
            num[i] = -1 ;
        cin >> n ;
        for(int i = 0 ; i < n ; i++){
            cin >> temp ;
            if( num[temp] >= last){

                //debug
                //cout << "debug: " <<  i << " last: " << last << '\n' ;

                ans++ ;
                last = i ;

            }
            num[temp] = i ;
        }
        cout << ans << '\n' ;
    }

    return 0;
}