hdu 4352 XHXJ's LIS （数位dp） - c++编程基础

TOP

hdu 4352 XHXJ's LIS （数位dp）(二)

2015-07-20 18:05:42 来源: 作者: 【大中小】浏览:8次

的LIS是1 2 4 6，这时候下一个数是3,那么我们就要更新成1 2 3 6,让前面的数尽可能的小，这样就是为了能让后面的数有更多的机会被加入。
因为数字只有10个，我们可以状态压缩，记录每个数字是否出现在当前的LIS中。 dp[i][j][k]：位数为i 当前LIS的状态为j 要求的上升子序列的长度为k。枚举当前位是什么来进行转移，注意考虑前导0和是否有上界标记。 k不是LIS的长度，一个状态的LIS长度是一定的，但对于要求的不同的LIS长度，一个状态得到的结果是不同的，所以k为要求的上升子序列的长度。
代码：

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               #define maxn 205 #define MAXN 100005 #define mod 100000000 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; ll n,m,ans,tot,le,ri,k; ll dig[20],dp[20][1<<11][11]; ll getstate(ll s,ll u,ll& xx) // 状态转移 { ll i,ss; for(i=u;i<10;i++) { if(s&(1<

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ3468A Simple Problem with In..	下一篇：hdu 4858 项目管理（图的分治）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: