Fork me on GitHub

1045 Favorite Color Stripe (30分)

发表于 | 分类于 | 次阅读
字数统计: 427 | 阅读时长 ≈ 1

PTA甲级 1045 Favorite Color Stripe (30分)

  • 找到最大长度的颜色序列
  • 顺序要正确，可以缺少颜色

由于要求最大长度，所以肯定要把每一个元素都遍历。

可以发现，只要一个颜色序列包括这个颜色（假设为i），那么我们可以求出这个序列最开始的颜色到这个颜色i的最大长度，用dp表示如果这个颜色i被选中，那么这个序列最开始的颜色到颜色i的最大长度，一开始初始化为1。接下来从1到i遍历（即遍历颜色i之前的颜色），只要i之前的颜色j的等级不大于i（即j <= i），那么就更新dp[i] = max(dp[i] , dp[j]+1)，也就是说，我们要想让颜色序列包括颜色i，那么颜色i之前的颜色j的等级就必须<=，这样从1到i遍历后，我们就可以找到如果序列包括颜色i时的最大长度。

关键：dp[i] = max(dp[i] , dp[j]+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

vector<int> order , v;
int book[201];
vector<int> position[300];
int dp[10010];
int main()
{
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    int m;
    cin>>m;
    for(int i = 1 ; i<=m ; ++i){
        int a;
        cin>>a;
        book[a] = i;
    }
    int L;
    cin>>L;
    for(int i = 0 ; i<L ; ++i){
        int a;
        cin>>a;
        if(book[a]){
            v.push_back(book[a]);
        }
    }
    
    int mmax = -1;
    for(int i = 0 ; i<v.size() ; ++i){
        dp[i] = 1;
        for(int j = 0 ; j<i ; ++j){
            if(v[i] >= v[j]){
                dp[i] = max(dp[i] , dp[j]+1);
            }
        }
        mmax = max(mmax , dp[i]);
    }
    cout<<mmax;
}