HDU_5125

描述

一个双轨LIS。即可以用b[i]代替a[i]，但是次数不能超过魔法值。

思路

一开始是没有什么思路，傻傻想到了dp，但是脑子一团浆糊。后来杜康晖大大和我讲了一下LIS的dp做法，脑子就开窍了。感谢老杜啦。

AC代码

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
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1008][2][2],a[1008],b[1008];
int main(){
    int T,n,s;for(cin>>T;T;T--){
        cin>>n>>s;
        memset(dp,0,sizeof(dp));
        for(int i=1; i <=n ;i++){
            scanf("%d%d",&a[i],&b[i]);
            dp[i][0][0]=1;dp[i][1][0]=1;
        }
        dp[1][1][1]=1;
        for(int i=1 ; i<=n ; i++){
            for(int j=1 ; j<i ;j++){
               if(a[j]<a[i]){
                    if(dp[j][0][0]+1>dp[i][0][0]){
                        dp[i][0][0]=dp[j][0][0]+1;
                        dp[i][0][1]=dp[j][0][1];
                    }
               } 
               if(a[j]<b[i]){
                    if(dp[j][0][0]+1>dp[i][1][0]){
                        dp[i][1][0]=dp[j][0][0]+1;
                        dp[i][1][1]=dp[j][0][1]+1;
                    }
               }
               if(b[j]<a[i]){
                    if(dp[j][1][0]+1>dp[i][0][0]){
                        dp[i][0][0]=dp[j][1][0]+1;
                        dp[i][0][1]=dp[j][1][1];
                    }
               }
               if(b[j]<b[i]){
                    if(dp[j][1][0]+1>dp[i][1][0]){
                        dp[i][1][0]=dp[j][1][0]+1;
                        dp[i][1][1]=dp[j][1][1]+1;
                    }
               }
            }
        }
        int ans=0;
        for(int i=1; i <= n ;i++){
            if(dp[i][0][1]<=s)ans=max(ans,dp[i][0][0]);
            if(dp[i][1][1]<=s)ans=max(ans,dp[i][1][0]);
        }
        printf("%d\n",ans);
    }
    return 0;
}