HOJ 2631. Training of Lord Fish’s Fan II

Posted on by

Brief description :

卡搜索，卡DP的0/1背包問題。
(N<=30, M<=1,000,000,000)

Analyse :

減半合併，參見前文，相比子集和問題，0/1背包拼答案的時候要開兩個指針，
一頭一尾向中間掃描，另外需要注意的則是 merge() 前的一段。

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

#include 
#include 
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);
    else{
        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);
    merge();
}

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

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