CF294B Shaass and Bookshelf（Jan. 18th, 2019） 创造性

动态规划

• CF294B Shaass and Bookshelf（Jan. 18th, 2019） 创造性
  • 题意
  • 思路
  • 反思
  • 代码

题目来源

题意

$La\ Pluie$想以优雅强迫症的方式放置$n\in [1, 100]$本厚度$t_i\in \{1, 2\}$的书籍，书籍宽度$w_i\in [1, 100]$不一定相等，但高度一致。放不下的书可以放在所有书的顶上，但是要保证顶上的书的总宽度不超过书架宽度。求能放下书[1]）的最小书架宽度。

思路

$dp[i][j][k]$表示放第$i$本书时，厚度总和为$j$，宽度总和为$k$时的情况是否成立。

$$if(j>=t[i])\quad dp[i][j][k]|=dp[i-1][j-t[i]][k]$$ $$if(k>=w[i])\quad dp[i][j][k]|=dp[i-1][j][k-w[i]]$$
滚动数组压掉$i$维，$j、k$维边界为200，因为书籍总厚度最大为200，故答案只可能在这个区间内（易证不会有超出200的答案）。

反思

1. 很多题都很显然，只是需要去仔细推算。

代码

// La Pluie
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100 + 5;
int dp[N][N << 1][N << 1], t[N], w[N];
int main(){
    int n;
    scanf("%d", &n);
    int T = 0, W = 0;
    for(int i = 1; i <= n; i++){
        scanf("%d %d", &t[i], &w[i]);
        T += t[i]; W += w[i];
    }
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= T; j++){
            for(int k = 0; k <= min(W, 200); k++){
                if(j >= t[i]) dp[i][j][k] |= dp[i - 1][j - t[i]][k];
                if(k >= w[i]) dp[i][j][k] |= dp[i - 1][j][k - w[i]];
            }
        }
    }
    int ans = 200;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= T; j++){
            for(int k = 0; k <= min(W, 200); k++){
                if(k > j) break;
                if(dp[n][j][k]) ans = min(ans, max(j, k));
            }
        }
    }
    printf("%d", ans);
    return 0;
}