固定模板
不记录路径
#include <bits/stdc++.h>
using namespace std
;
const int N
= 100;
int A
[N
], dp
[N
];
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
++)
{
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
;
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
++)
{
if(hashTable
[A
[i
]] >= hashTable
[A
[j
]] && dp
[i
] < dp
[j
] + 1)
{
dp
[i
] = dp
[j
] + 1;
}
}
ans
= max(ans
, dp
[i
]);
}
cout
<< ans
;
return 0;
}
