Codeforces 294B Shaass and Bookshelf：dp

题目链接：http://codeforces.com/problemset/problem/294/B

题意：

　　有n本书，每本书的厚度为t[i]，宽度为w[i] (1<=t[i]<=2, 1<=w[i]<=100)。

　　然后让你将所有书按照下面的方式摆放：

　　在下面放一本书会占用下面t[i]的长度。

　　在上面放一本书会占用上面w[i]的长度。

　　最终要保证上面的总长度不超过下面的总长度。

　　问你下面的总长度最小是多少。

题解：

　　表示状态：

　　　　dp[i][j] = min length

　　　　表示已经放了前i本书，下面的总长度为j时，上面的最小总长度。

　　找出答案：

　　　　ans = min i (dp[n][i]<=i)

　　如何转移：

　　　　对于第i本书，要么放上面，要么放下面。

　　　　dp[i][j] = min(dp[i-1][j]+w[i], dp[i-1][j-t[i]])

　　边界条件：

　　　　set dp = INF

　　　　dp[0][0] = 0

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 105

 #define MAX_T 205

 #define INF 1000000000

 using namespace std;

 int n;

 int t[MAX_N];

 int w[MAX_N];

 int dp[MAX_N][MAX_T];

 int main()

 {

     cin>>n;

     for(int i=;i<=n;i++)

     {

         cin>>t[i]>>w[i];

     }

     memset(dp,0x3f,sizeof(dp));

     dp[][]=;

     int tot=;

     for(int i=;i<=n;i++)

     {

         tot+=t[i];

         for(int j=;j<=tot;j++)

         {

             dp[i][j]=min(dp[i][j],dp[i-][j]+w[i]);

             if(j-t[i]>=) dp[i][j]=min(dp[i][j],dp[i-][j-t[i]]);

         }

     }

     int ans=INF;

     for(int i=;i<=tot;i++)

     {

         if(dp[n][i]<=i) ans=min(ans,i);

     }

     cout<<ans<<endl;

 }

巴特西

Codeforces 294B Shaass and Bookshelf：dp

最新文章

热门文章