本文共 1118 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

给出n本书，每本书有长和宽，先立着放一排，然后在顶上再倒着放，问立着放的这一排最短的距离是多少。

题目分析:

• 定义状态dp[i][j][k]表示第i本书构成立着排长度为j，横着的排长度为k的情况是否存在。
• 转移方程很简单,见代码。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 107using namespace std;int n,dp[MAX][MAX<<1][MAX<<1],t[MAX],w[MAX];int main ( ){    while ( ~scanf ( "%d" , &n ) )    {        for ( int i = 1 ; i <= n ; i++ )            scanf ( "%d %d" , &t[i] , &w[i] );        memset ( dp , 0 , sizeof ( dp ) );        dp[0][0][0] = 1;        for ( int i = 1 ; i <= n ; i++ )            for ( int j = 0 ; j <= 2*n ; j++ )               for ( int k = 0 ; k <= 2*n; k++ )               {                   if ( j >= t[i] && dp[i-1][j-t[i]][k] )                        dp[i][j][k] = 1;                   if ( k >= w[i] && dp[i-1][j][k-w[i]] )                       dp[i][j][k] = 1;               }        bool flag = true;        for ( int i = 0 ; i <= 200&&flag ; i++ )           for ( int k = 0 ; k <= i&&flag ; k++ )               if ( dp[n][i][k] )               {                   printf ( "%d\n" , i );                   flag = false;               }    }}
      
     
    
   

转载地址：http://dqvjn.baihongyu.com/