JAG 模擬地区予選 2011 B問題

解法

BitDP

実装(C++)

A問題よりも実装時間が短かった気がする．

#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <iomanip>
#include <functional>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iterator>
#include <sstream>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define FOR(it,x) for(__typeof(x.begin()) it=x.begin();it!=x;it++)
int N;
struct Guy{
        int M,L;
        vector<int> S,E;
        int state;
};
Guy guys[100];
bool input(){
        cin>>N;
        if(N==0)return false;
        for(int i=0;i<N;i++){
                int M,L;
                cin>>M>>L;
                guys[i]=Guy();
                guys[i].M=M;
                guys[i].L=L;
                guys[i].state=0;
                guys[i].S=vector<int>();
                guys[i].E=vector<int>();

                REP(j,M){
                        int s,e;
                        cin>>s>>e;
                        guys[i].S.push_back(s);
                        guys[i].E.push_back(s);
                        for(int k=s;k<e;k++){
                                guys[i].state|=1<<k;
                        }
                }
        }
        return true;
}
unordered_map<int,long long> res[100];
long long solve(int k,int state){
        if(k==N){
                return 0;
        }
        if(res[k].find(state)!=res[k].end())return res[k][state];
        long long ans=solve(k+1,state);
        //state=0
        //使う
        if((state&guys[k].state)==0){
                ans=max(ans,solve(k+1,state|guys[k].state)+guys[k].L);
        }
        return res[k][state]=ans;
}
int main() {
        while(input()){
                REP(i,100){
                        res[i].clear();
                }
                cout<<solve(0,0)<<endl;
        }
        return 0;
}