HOJ 2631. Training of Lord Fish’s Fan II

Brief description :

(N<=30, M<=1,000,000,000)

Analyse :

一头一尾向中间扫描,另外需要注意的则是 merge() 前的一段。

    Author: xiaodao
    Prog: HOJ 2631. Training of Lord Fish's Fan II
    Status: Accepted
    Last modifiy: GMT +8 Aug. 28th 10:29

using namespace std;
const int N = 30;
map h1, h2;
int C[N], V[N]; //cost value
int n, m, step, ans;
       // depth, cost, value, hash pointer..
void dfs(int k, int c, int v, map &h){
    if (c>m) return;
    if (k==step) h = max(h, v);
        dfs(k+1, c+C[k], v+V[k], h);
        dfs(k+1, c, v, h);

void merge(){
    map::iterator i;
    map::reverse_iterator ii;

    ans = max(h1.rbegin()->second, h2.rbegin()->second);

    for (i=h1.begin(), ii = h2.rbegin();i!=h1.end();i++){
        while (ii!=h2.rend() && i->first + ii->first > m) ii++;
        if (ii==h2.rend()) return;
        //printf("%u %d\n", it->first, it->second);
        //printf("%u %d\n", itt->first, itt->second);
        ans = max(ans, i->second + ii->second);

void solve(){
    step = n/2; dfs(0, 0, 0, h1);
    step = n; dfs(n/2, 0, 0, h2);

    map::iterator i, ii;
    for (i=h1.begin(),ii=i,ii++;ii!=h1.end();i++,ii++)
        ii->second = max(i->second, ii->second);
    for (i=h2.begin(),ii=i,ii++;ii!=h2.end();i++,ii++)
        ii->second = max(i->second, ii->second);

void init(){
    scanf("%d %d", &n, &m);

    int x, y;
    for (int i=0;i> T;
    while (T--){
        init(); solve();
        cout << ans << endl;