注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-3042: Acting Cute(环状DP转线性DP)  

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

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3042


方程:

f[ i ][ j ][ 0 ] = max( f[ i - 1 ][ j ][ 0 ] , f[ i - 1 ][ j ][ 1 ] )

f[ i ][ j ][ 1 ] = max( f[ i - 1 ][ j - 1 ][ 1 ] + u i , f[ i - 1 ][ j - 1 ][ 0 ] )

然后第一次令f[ 1 ][ 0 ][ 0 ] = f[ 1 ][ 1 ][ 1 ] = 0 ,目标状态f[ n ][ m ][ 0 ] , f[ n ][ m ][ 1 ]

然后再令f[ 1 ][ 1 ][ 1 ] = u[ 1 ] ,再做一次DP,目标状态f[ n ][ min( n - 1 , m ) ][ 1 ]


代码:

BZOJ-3042: Acting Cute(环状DP转线性DP) - cjjlsdy - cjjlsdy的博客

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define MAXN 4010
  • #define inf 0x7fffffff
  •  
  • int f[ MAXN ][ MAXN ][ 2 ] , n , m , u[ MAXN ] , ans = - inf ;
  •  
  • int main(  ) {
  •     scanf( "%d%d" , &n , &m ) ; for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , &u[ i ] ) ;
  •     for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j <= m ; j ++ ) f[ i ][ j ][ 0 ] = f[ i ][ j ][ 1 ] = - inf ;
  •     f[ 1 ][ 0 ][ 0 ] = f[ 1 ][ 1 ][ 1 ] = 0 ;
  •     for ( int i = 1 ; i ++ < n ; ) {
  •         for ( int j = 0 ; j <= m ; j ++ ) {
  •             f[ i ][ j ][ 0 ] = max( f[ i - 1 ][ j ][ 1 ] , f[ i - 1 ][ j ][ 0 ] ) ;
  •             if ( j ) f[ i ][ j ][ 1 ] = max( f[ i - 1 ][ j - 1 ][ 1 ] + u[ i ] , f[ i - 1 ][ j - 1 ][ 0 ] ) ;
  •         }
  •     }
  •     ans = max( ans , max( f[ n ][ m ][ 0 ] , f[ n ][ m ][ 1 ] ) ) ;
  •     for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j <= m ; j ++ ) f[ i ][ j ][ 0 ] = f[ i ][ j ][ 1 ] = - inf ;
  •     f[ 1 ][ 1 ][ 1 ] = u[ 1 ] ;
  •     for ( int i = 1 ; i ++ < n ; ) {
  •         for ( int j = 0 ; j <= m ; j ++ ) {
  •             f[ i ][ j ][ 0 ] = max( f[ i - 1 ][ j ][ 1 ] , f[ i - 1 ][ j ][ 0 ] ) ;
  •             if ( j ) f[ i ][ j ][ 1 ] = max( f[ i - 1 ][ j - 1 ][ 1 ] + u[ i ] , f[ i - 1 ][ j - 1 ][ 0 ] ) ;
  •         }
  •     }
  •     ans = max( ans , f[ n ][ min( n - 1 , m ) ][ 1 ] ) ;
  •     printf( "%d\n" , ans ) ;
  •     return 0 ; 
  • }


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

历史上的今天

评论

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

页脚

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