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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1084: [SCOI2005]最大子矩阵(DP)  

2014-03-23 15:11:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


开始是以为是什么神题,后来发现m<=2那就直接DP O(n^3)水掉了。。。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

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

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

  •  

  • const int maxn =110, maxm =3, maxk =15;

  •  

  • int n , m , k ;

  •  

  •  

  • void solve0(  ){

  •     int a[ maxn ], sum[ maxn ], f[ maxn ][ maxk ];

  •     bool u[ maxn ][ maxk ];

  •     sum[0]=0;

  •     rep( i , n ){

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

  •         sum[ i ]= sum[ i -1]+ a[ i ];

  •     }

  •     memset( f ,0,sizeof( f ));

  •     memset( u ,false,sizeof( u ));

  •     u[0][0]=true;

  •     rep( i , n )Rep( j , k +1){

  •         if( u[ i -1][ j ]){

  •             u[ i ][ j ]=true, f[ i ][ j ]= f[ i -1][ j ];

  •         }

  •         if( j )Rep( x , i )if( u[ x ][ j -1]){

  •             u[ i ][ j ]=true;

  •             f[ i ][ j ]=max( f[ i ][ j ], f[ x ][ j -1]+ sum[ i ]- sum[ x ]);

  •         }

  •     }

  •     int ans =0;

  •     rep( i , n )if( u[ i ][ k ]) ans =max( ans , f[ i ][ k ]);

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

  • }

  •  

  • int a[ maxn ][ maxm ], sum[ maxn ][ maxm ], f[ maxn ][ maxn ][ maxk ];

  • bool u[ maxn ][ maxn ][ maxk ];

  •  

  • void solve1(  ){

  •     sum[0][1]= sum[0][2]=0;

  •     rep( i , n ){

  •         scanf("%d%d",&a[ i ][1],&a[ i ][2]);

  •         sum[ i ][1]= sum[ i -1][1]+ a[ i ][1];

  •         sum[ i ][2]= sum[ i -1][2]+ a[ i ][2];

  •     }

  •     memset( f ,0,sizeof( f ));

  •     memset( u ,false,sizeof( u ));

  •     u[0][0][0]=true;

  •     Rep( i , n +1)Rep( j , n +1)if( i || j ){

  •         Rep( h , k +1){

  •             if( i )if( u[ i -1][ j ][ h ]){

  •                 u[ i ][ j ][ h ]=true;

  •                 f[ i ][ j ][ h ]= f[ i -1][ j ][ h ];

  •             }

  •             if( j )if( u[ i ][ j -1][ h ]){

  •                 u[ i ][ j ][ h ]=true;

  •                 f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ i ][ j -1][ h ]);

  •             }

  •             if( h ){

  •                 Rep( x , i )if( u[ x ][ j ][ h -1]){

  •                     u[ i ][ j ][ h ]=true;

  •                     f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ x ][ j ][ h -1]+ sum[ i ][1]- sum[ x ][1]);

  •                 }

  •                 Rep( y , j )if( u[ i ][ y ][ h -1]){

  •                     u[ i ][ j ][ h ]=true;

  •                     f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ i ][ y ][ h -1]+ sum[ j ][2]- sum[ y ][2]);

  •                 }

  •                 if( i == j )Rep( x , i )if( u[ x ][ x ][ h -1]){

  •                     u[ i ][ j ][ h ]=true;

  •                     f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ x ][ x ][ h -1]+( sum[ i ][1]- sum[ x ][1])+( sum[ j ][2]- sum[ x ][2]));

  •                 }

  •             }

  •         }

  •     }

  •     int ans =0;

  •     Rep( i , n +1)Rep( j , n +1)if( u[ i ][ j ][ k ]){

  •         ans =max( ans , f[ i ][ j ][ k ]);

  •     }

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

  • }

  •  

  • int main(  ){

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

  •     if( m ==1)solve0(  );else solve1(  );

  •     return 0;

  • }



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

历史上的今天

评论

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

页脚

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