Codeforces Round #178 (Div. 2) B - Shaass and Bookshelf

 

DP

dp[i] i表示厚度，而dp[i]的值是這個厚度當中 寬度最大的為多少

之後再用總數去扣掉即可

 

貌似有greedy解法，分成厚度1跟2 具體內容要參考其他blog

/*
 * GCA : Where is the Dp,there is the wall
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) decltype(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(__VA_ARGS__)
#else
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...)
#endif
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\n")
#define M 104
#define PB push_back
#define oo (1<<29)
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
int n;
int t[M];
int w[M];
int dp[2*M];
int main() {
    ios_base::sync_with_stdio(0);
    while(~scanf("%d",&n)){
        int all=0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&t[i],&w[i]);
            all+=w[i];
        }
        for(int i=0;i<=200;i++)dp[i]=-oo;
        dp[0]=0;
        for(int i=0;i<n;i++){
            for(int j=200;j>=t[i];j--){
                dp[j]=max(dp[j],dp[j-t[i]]+w[i]);
            }
        }
        int i;
        for(i=0;i<=200;i++){
            if(i>=all-dp[i])break;
        }
        printf("%d\n",i);
    }

















}