hdu--5124--5125-bc

这2题放一起吧反正都是同一场的.

B题虽然是被自己想复杂了用了树状数组。。

当时自己还没离散化出来还是用了超神的离散化 ‘

不知道自己的哪边错了 ffffffk

<区间更新单点查询>

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int res;
 7 const int size = 100010*3;
 8 struct data
 9 {
10     int L;
11     int R;
12 }node[size];
13 int lisan[size] , a[size] , tree[size];
14 
15 int lowBit( int x )
16 {
17     return x & -x;
18 }
19 
20 void update( int index , int var )
21 {
22     while( index<=res )
23     {
24         tree[index] += var;
25         index += lowBit( index );
26     }
27 }
28 
29 int getSum( int index )
30 {
31     int sum = 0;
32     while( index )
33     {
34         sum += tree[index];
35         index -=lowBit( index );
36     }
37     return sum;
38 }
39 
40 int main()
41 {
42     cin.sync_with_stdio(false);
43     int t , n , ans , cnt;
44     cin >> t;
45     while( t-- )
46     {
47         cin >> n;
48         memset( tree , 0 , sizeof(tree) );
49         res = cnt = 1;
50         for( int i = 1 ; i<=n ; i++ )
51         {
52             cin >> node[i].L >> node[i].R;
53             a[cnt++] = node[i].L;
54             a[cnt++] = node[i].R;
55         }
56         sort( a+1 , a+cnt );
57         for( int i = 1 ; i<cnt ; i++ )
58         {
59             if (i == 1)
60             {
61                 lisan[a[i]] = ++res;
62             }
63             else if (a[i] == a[i - 1])
64             {
65                 lisan[a[i]] = lisan[a[i - 1]];
66             }
67             else
68             {
69                 lisan[a[i]] = ++res;
70             }
71         }
72         for( int i = 1 ; i<=n ; i++ )
73         {
74             update(  lisan[ node[i].L ] , 1 );
75             update( lisan[ node[i].R ]+1 , -1 );
76         }
77         ans = 0;
78         for( int i = 1 ; i<=cnt ; i++ )
79         {
80             ans = max( ans , getSum(i) );
81         }
82         cout << ans << endl;
83     }
84     return 0;
85 }

View Code

这题最好的解决方法吧应该是这个吧

 1 #include <iostream>
 2 #include <vector>
 3 #include <utility>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 vector< pair<int,int> >ve;
 8 
 9 int main( )
10 {
11     cin.sync_with_stdio(false);
12     int t , n , ans , sum , x , y , veSize;
13     cin >> t;
14     while( t-- )
15     {
16         cin >> n;
17         ve.clear();
18         for( int i = 0 ; i<n ; i++ )
19         {
20             cin >> x >> y;
21             ve.push_back( make_pair(x,1) );
22             ve.push_back( make_pair(y+1,-1) );
23         }
24         ans = sum = 0;
25         veSize = ve.size();
26         sort( ve.begin() , ve.end() );
27         for( int i = 0 ; i<veSize ; i++ )
28         {
29             sum += ve[i].second;
30             ans = max( ans , sum );
31         }
32         cout << ans << endl;
33     }
34     return 0;
35 }

View Code

另外一个dp还没出明天再想吧累。。。

第一次碰到需要使用线段树或者树状数组来维护dp。。太渣 ...

参考了传送

自己也写了遍自己代码风格的代码

dp[x,y]表示操作数还剩余x次以y结尾的最大子序列长度

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int tot;
 7 const int size = 2010;
 8 int tree[size][size];
 9 int a[size] , b[size] , c[size];
10 
11 int lowBit( int x )
12 {
13     return x & -x ;
14 }
15 
16 void update( int oper , int index , int var )
17 {
18     while( index<=tot )
19     {
20         tree[oper][index] = max( tree[oper][index] , var );
21         index += lowBit( index );
22     }
23 }
24 
25 int getSum( int oper , int index )
26 {
27     int sum = 0;
28     while( index )
29     {
30         sum = max( sum , tree[oper][index] );
31         index -= lowBit( index );
32     }
33     return sum;
34 }
35 
36 int main()
37 {
38     cin.sync_with_stdio(false);
39     int t , n , m , temp , ans;
40     cin >> t;
41     while( t-- )
42     {
43         cin >> n >> m;
44         ans = tot = 1;
45         for( int i = 0 ; i<n ; i++ )
46         {
47             cin >> a[i] >> b[i];
48             c[ tot++ ] = a[i];
49             c[ tot++ ] = b[i];
50         }
51         memset( tree , 0 , sizeof(tree) );
52         sort( c+1 , c+tot );
53         tot = unique( c+1 , c+tot ) - c;
54         for( int i = 0 ; i<n ; i++ )
55         {
56             a[i] = lower_bound( c+1 , c+tot , a[i] ) - c;
57             b[i] = lower_bound( c+1 , c+tot , b[i] ) - c;
58         }
59         for( int i = 0 ; i<n ; i++ )
60         {
61             for( int j = 0 ; j<=m ; j++ )
62             {
63                 temp = getSum( j , a[i]-1 ) + 1;
64                 update( j , a[i] , temp );
65                 ans = max( temp , ans );
66                 if( j<m )
67                 {
68                     temp = getSum( j+1 , b[i]-1 ) + 1;
69                     update( j , b[i] , temp );
70                     ans = max( temp , ans );
71                 }
72             }
73         }
74         cout << ans << endl;
75     }
76     return 0;
77 }

View Code

当然我也可以将dp[x,y]定义为操作了x次后以y结尾的最大子序列长度只要这样修改一下

 1         for( int i = 0 ; i<n ; i++ )
 2         {
 3             for( int j = m ; j>=0 ; j-- )
 4             {
 5                 temp = getSum( j , a[i]-1 ) + 1;
 6                 update( j , a[i] , temp );
 7                 ans = max( temp , ans );
 8                 if( j )
 9                 {
10                     temp = getSum( j-1 , b[i]-1 ) + 1;
11                     update( j , b[i] , temp );
12                     ans = max( temp , ans );
13                 }
14             }
15         }

这边有个地方一定要注意

就是对于次数m的遍历当我们定义为剩余x次操作的时候是顺序遍历的

当我定义为已经操作了已经操作了x次的时候是要逆序遍历的

但我无法很好的解释如果谁能给个清晰的解释不妨留下评论 thx