多米诺骨牌

现有n块”多米诺骨牌”s1,s2,s3,...sn水平放成一排,每次骨牌si包含左右两个部分,每个部分赋予一个非负整数值,如下图所示为包含6块骨牌的序列.骨牌可做180度旋转,使得原来在左边的值变到右边,而原来右边的值移到左边,假设不论si如何旋转,L[i]总是存储si左边的值, R[i]总是存储si右边的值, W[i]用于存储si的状态:当L[i]<=R[i]时记为0,否则记为1,试采用动态规划算法设计时间复杂度为o(n)的算法

 求:R[1]*L[2]+R[2]*L[3]+R[3]*L[4]+R[4]*L[5]+...++R[n-1]*L[n]的最大值,以及当取得最大值时每个骨牌的状态.
  5|8    4|2     9|6    7|7   3|9    11|10

  s1       s2     s3      s4    s5        s6

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      const 
      int N=
      100;
     
    
   

    

     

    
    

     

      using 
      namespace 
      std ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 
      int i,j,n,a,b,c,d,ans=
      0;
     
    
   

    

     

    
    

     
 
      int l[N],r[N],m[
      2][N]={
      0},w[N]={
      0},p[
      2][N]={
      0};
     
    
   

    

     

    
    

     
 
      cin>>n;
     
    
   

    

     

    
    

     
 
      for(i=
      1;i<=n;i++) 
      cin>>l[i]>>r[i];
     
    
   

    

     

    
    

     

       m[
      0][
      1]=m[
      1][
      1]=
      0;
     
    
   

    

     

    
    

     
 
      for(i=
      1;i<n;i++)
      //
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 
      // a|b c|d
     
    
   

    

     

    
    

     
 
      // si si+1
     
    
   

    

     

    
    

     

       a=l[i],b=r[i];
     
    
   

    

     

    
    

     

       c=l[i+
      1],d=r[i+
      1];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
      if((m[
      0][i]+b*c)>(m[
      1][i]+a*c))
     
    
   

    

     

    
    

     

       m[
      0][i+
      1]+=m[
      0][i]+b*c,p[
      0][i+
      1]=
      0;
     
    
   

    

     

    
    

     
 
      else m[
      0][i+
      1]+=m[
      0][i]+a*c,p[
      0][i+
      1]=
      1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
      if((m[
      0][i]+b*d)>(m[
      1][i]+a*d))
     
    
   

    

     

    
    

     

       m[
      1][i+
      1]+=m[
      0][i]+b*d,p[
      1][i+
      1]=
      0;
     
    
   

    

     

    
    

     
 
      else m[
      1][i+
      1]+=m[
      0][i]+a*d,p[
      1][i+
      1]=
      1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
      if(m[
      0][n]>m[
      1][n]) w[n]=
      0,
      cout<<m[
      0][n]<<
      endl;
     
    
   

    

     

    
    

     
 
      else w[n]=
      1,
      cout<<m[
      1][n]<<
      endl;
     
    
   

    

     

    
    

     
 
      for(i=n;i>
      1;i--)
     
    
   

    

     

    
    

     
 
      if(w[i]==
      0) w[i
      -1]=p[
      0][i];
     
    
   

    

     

    
    

     
 
      else w[i
      -1]=p[
      1][i];
     
    
   

    

     

    
    

     
 
      for(i=
      1;i<=n;i++) 
      cout<<w[i]<<
      " ";
     
    
   

    

     

    
    

     

      }