UVa12385 - Interesting Sequences (水題)

2020-04-28

UVa

字數統計： 352 | 閱讀時間≈ 1分鐘

題目大意：
分析：
1. DP規則如下( 透過 greedy 優化 )：
  1. 題外話:

題目大意：

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

分析：

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

「Interesting Sequences」定義如下:

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

ex1: 4 2 3 5 9 2 1

2 3 5 9 2

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

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

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

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

透過陣列記住每個數字最後的位置
last 做為上次 Interesting Sequences 的最後 index，因為 Interesting Sequences 不可以重疊。
如果數字最後的位置 >= 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;
}

版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！