SRM 195 DIV2 FanFailure

 

 

算滿水的題目，不過題意讀得很累

/*
 * GCA : "Computer is artificial subject absolutely,Math is God"
 */
#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) decltype(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 50005
#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
#define X first
#define Y second
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;}

const Int mod=1000000007;


class FanFailure {
    int dp[M];

    int mfs,mfc;
    public: vector<int> getRange(vector<int> capacities, int minCooling) {
        fill(&dp[0],&dp[M-1],oo);
        dp[0]=0;
        int all=0;
        sort(capacities.begin(),capacities.end());
        FOR(it,capacities){
            all+=(*it);
        }
        for(int i=0;i<capacities.size();i++){
            for(int j=all;j>=capacities[i];j--){
                int x=j-capacities[i];
                dp[j]=min(dp[j],dp[x]+1);
            }
        }
        int minn=oo;
        for(int i=minCooling;i<=all;i++){
//            debug("%d\n",dp[i]);
            minn=min(minn,dp[i]);
        }
        mfs=capacities.size()-minn;
        int now=all;
//        mfc=capacities.size();
        for(int i=capacities.size()-1,k=0;i>=0;i--,k++){
            if(now<minCooling){
                mfc=k-1;
                break;
            }
            now-=capacities[i];
            if(i==0&&now<minCooling){
                mfc=k;
                break;
            }
        }
        vector<int> ans;
        ans.PB(mfs);ans.PB(mfc);
        return ans;
    }

};