- Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and she can use these to win at most 3 points. For example, she can defeat the 1 card and then switch the rules to "low card wins", after which she can win two more rounds.
- Solution
做法:$set+dp+$ 贪心
首先容易想到一个思路, 在点数大能赢的情况下尽量用数偏小的, 在点数小能赢的情况下尽量用数偏大的
这个用 $set$ 维护
然后设 $f[i]$ 表示前 $i$ 轮为点数大能赢时能赢的最多次数
$g[i]$ 表示后面 $i~n$ 轮为点数小能赢时能赢得最多次数
所以答案就是 $max(f[i]+g[i+1])$
但是这个贪心好像有个问题, 就是你一张牌子, 可能在上一轮和这一轮都用过一次
其实是没问题... 因为你用了两次这张牌, 设它为 $x$, 那么肯定还有一牌 $y$ 没有用, 当 $x>y$ 时, 这张 $y$ 就可以在后面用, 反之就在前面用
- #include <cstdio>
- #include <set>
- using namespace std ;
- #define N 100010
- int f[ N ] , g[ N ] ;
- int n , a[ N ] ;
- bool vis[ N ] ;
- set<int> s , t ;
- int main() {
- scanf( "%d" , &n ) ;
- for( int i = 1 ; i <= n ; i ++ ) {
- scanf( "%d" , &a[ i ] ) ;
- vis[ a[ i ] ] = 1 ;
- }
- for( int i = 1 ; i <= 2 * n ; i ++ ) {
- if( ! vis[ i ] ) s.insert( i ) , t.insert( -i ) ;
- }
- for( int i = 1 ; i <= n ; i ++ ) {
- set<int> :: iterator it = s.upper_bound( a[ i ] ) ;
- if( it != s.end() ) f[ i ] = f[ i - 1 ] + 1 , s.erase( *it ) ;
- else f[ i ] = f[ i - 1 ] ;
- }
- for( int i = n ; i ; i -- ) {
- set<int> :: iterator it = t.upper_bound( -a[ i ] ) ;
- if( it != t.end() ) g[ i ] = g[ i + 1 ] + 1 , t.erase( *it ) ;
- else g[ i ] = g[ i + 1 ] ;
- }
- int ans = 0 ;
- for( int i = 0 ; i <= n ; i ++ ) {
- ans = max( ans , f[ i ] + g[ i + 1 ] ) ;
- }
- printf( "%d\n" , ans ) ;
- }
来源: http://www.bubuko.com/infodetail-2784999.html