注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1786: [Ahoi2008]Pair 配对 && 1831: [AHOI2008]逆序对 (DP)  

2014-06-09 21:01:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:

http://www.lydsy.com/JudgeOnline/problem.php?id=1786

http://www.lydsy.com/JudgeOnline/problem.php?id=1831


我们可以神奇的证明出填入的数是单调不递减的(证明详解灰天飞雁大神的神题解:http://www.cnblogs.com/htfy/archive/2012/12/11/2813497.html),于是乎我们就可以很愉快的DP出来了。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  •  

  • const int maxn = 10010 , maxk = 110 , inf = 1000000000 ;

  •  

  • int dp[ maxn ][ maxk ] , pre[ maxn ][ maxk ] , a[ maxn ] , n , k , ans = 0 ;

  •  

  • int Count( int pos , int val ) {

  •     return ( pre[ pos ][ k ] - pre[ pos ][ val ] ) + ( pre[ n ][ val - 1 ] - pre[ pos ][ val - 1 ] ) ;

  • }

  •  

  • int main(  ) {

  •     memset( pre[ 0 ] , 0 , sizeof( pre[ 0 ] ) ) ;

  •     scanf( "%d%d" , &n , &k ) ;

  •     rep( i , n ) {

  •         scanf( "%d" , a + i ) ;

  •         REP( j , 0 , k ) pre[ i ][ j ] = pre[ i - 1 ][ j ] ;

  •         if ( a[ i ] != -1 ) ++ pre[ i ][ a[ i ] ] ;

  •     }

  •     rep( i , n ) rep( j , k ) pre[ i ][ j ] += pre[ i ][ j - 1 ] ;

  •     rep( i , n ) {

  •         if ( a[ i ] != -1 ) ans += ( pre[ i ][ k ] - pre[ i ][ a[ i ] ] ) ;

  •     }

  •     rep( i , k ) dp[ 0 ][ i ] = inf ;

  •     dp[ 0 ][ 1 ] = 0 ;

  •     int last = 0 , temp ;

  •     rep( i , n ) if ( a[ i ] == -1 ) {

  •         rep( j , k ) {

  •             temp = inf ;

  •             rep( h , j ) temp = min( temp , dp[ last ][ h ] ) ;

  •             dp[ i ][ j ] = min( inf , temp + Count( i , j ) ) ;

  •         }

  •         last = i ;

  •     }

  •     temp = inf ;

  •     rep( j , k ) temp = min( temp , dp[ last ][ j ] ) ;

  •     printf( "%d\n" , ans + temp ) ;

  •     return 0 ;

  • }


  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017