1045 Favorite Color Stripe (30分)[动态规划之最长不下降子序列]

固定模板

不记录路径

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int A[N], dp[N];//以A[i]为结尾的最长不下降子序列
int main()
{
    int n;cin >> n;for(int i = 1; i <= n; i++){
    cin >> A[i];}int ans = -1;for(int i = 1; i <= n; i++){
    dp[i] = 1; //假定最长子序列是自己for(int j = 1; j < i; j++) //判断要不要将i加进去 如果A[i]比A[j]高那肯定要加进去{
    if(A[i] >= A[j] && dp[i] < dp[j] + 1){
    dp[i] = dp[j] + 1;}}ans = max(dp[i], ans);}cout << ans;return 0;
}

题解

这道题其实就是换了模板里A[i] >= A[j]的判断标准，这道题可以把最喜欢的颜色顺序用数值映射一下，我第一次用了map超时了hhh 老老实实用个哈希表完事 其余就是模板
注意：

• 看清楚题 不是6个最喜欢的颜色 是5个 然后输入5个
• 要把不喜欢的颜色踢出去再用状态转移方程 不然如果第一个不是喜欢的颜色的话也可能被算进去

AC代码：

#include <bits/stdc++.h>
using namespace std;const int maxn = 10010;
int hashTable[maxn];
int A[maxn], dp[maxn];
int main()
{
    int n, m, l, x, k;cin >> n >> m; //n没用fill(hashTable, hashTable + maxn, -1);for(int i = 1; i <= m; i++){
    cin >> x;hashTable[x] = i;}cin >> l;int num = 1;for(int i = 1; i <= l; i++){
    cin >> x;if(hashTable[x] != -1){
    A[num++] = x;}}int ans = -1;for(int i = 1; i < num; i++){
    dp[i] = 1;for(int j = 1; j < i; j++) //不等于就是在做要不要i这个选择{
    if(hashTable[A[i]] >= hashTable[A[j]] && dp[i] < dp[j] + 1) //如果满足这个条件那就要把A[i]加到A[j]后边{
    dp[i] = dp[j] + 1;}}ans = max(ans, dp[i]);}cout << ans;return 0;
}