【PAT】A1045 Favorite Color Stripe (30分)（动态规划初级--两种方法LIS和LCS做）

1045 Favorite Color Stripe (30分)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn = 10004;int order[maxn];//喜欢的序列 
int stripe[maxn];//条纹序列 
int love[maxn] = {
    0};//love[i]=0:表示不喜欢i, love[i]=1:表示喜欢i,
int dp[maxn];
int N, M, L;//判断在喜欢的序列中，num1是否排在num2前边 
bool isFront(int num1, int num2)
{
    for(int i=0;i<M;i++)if(order[i] == num1)//考虑到了num1==num2返回true的情况 return true;else if(order[i] == num2)return false;return false;
}int main()
{
    cin>>N>>M;for(int i=0;i<M;i++){
    cin>>order[i];love[order[i]] = 1;}cin>>L;for(int i=0;i<L;i++){
    cin>>stripe[i];if(love[stripe[i]] == 0)//如果不是喜欢的颜色，直接置dp[i]=0 {
    dp[i] = 0;continue;	}else//如果是喜欢的颜色，先置dp[i]=1，然后再判断 dp[i] = 1;for(int j=0;j<i;j++){
    if(dp[j] == 0)//如果不是喜欢的颜色，跳过 continue;if(isFront(stripe[j], stripe[i])){
    //判断 dp[i] = max(dp[i], dp[j]+1);}}}cout<<*max_element(dp, dp+L)<<endl;return 0;} 

可惜：时间超时。
原因就在于：在喜欢的条纹序列中判断num1是否在num2前边，用的方法太麻烦了。

法二：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn = 10004;
const int maxc = 205; int order[maxc];
int stripe[maxn];
int love[maxc];
int dp[maxn];
int N, M, L;int main()
{
    memset(love, -1, sizeof(love));cin>>N>>M;for(int i=0;i<M;i++){
    cin>>order[i];love[order[i]] = i;//改进之处，置增序列}cin>>L;for(int i=0;i<L;i++){
    cin>>stripe[i];if(love[stripe[i]] == -1){
    dp[i] = 0;continue;	}dp[i] = 1;for(int j=0;j<i;j++){
    if(love[stripe[j]] != -1 && love[stripe[j]] <= love[stripe[i]]){
    //改进之处dp[i] = max(dp[i], dp[j]+1);}}}cout<<*max_element(dp, dp+L)<<endl;return 0;} 

终于AC。

还能再优化，明天再来补…

更新：
法三：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn = 10004;
const int maxc = 205; int order[maxc];
int stripe[maxn];
int stripe_love[maxn], num=0;
//stripe_love中存放the given stripe中喜欢的stripe 
int love[maxc];//判断是否喜欢 love[i]=0表示不喜欢i 
int dp[maxn];
int N, M, L;int main()
{
    memset(love, -1, sizeof(love));cin>>N>>M;for(int i=0;i<M;i++){
    cin>>order[i];love[order[i]] = i;//改进之处，置增序列}cin>>L;for(int i=0;i<L;i++){
    cin>>stripe[i];if(love[stripe[i]] != -1)stripe_love[num++] = stripe[i];}//stripe_love中全部存放的是喜欢的stripefor(int i=0;i<num;i++){
    dp[i] = 1;for(int j=0;j<i;j++){
    if(love[stripe_love[j]] <= love[stripe_love[i]]){
    //改进之处dp[i] = max(dp[i], dp[j]+1);}}}cout<<*max_element(dp, dp+L)<<endl;return 0;} 

其实，这道题还能依据LCS做出来，以后再来补。