随笔-141  评论-9  文章-3  trackbacks-0
USACO 5.3.1 Milk Measuring (DFSID+DP)

本题我采用DFS+DP的方法，题意是找使用最少的桶，所有先用1个桶进行DFS枚举，再用2个，3个，等等。

枚举出使用的桶之后，DP的环节就是完全背包问题。

初始化：f[i* v[第一个桶]]=true   (我试过仅f[0]也能过，就是慢点）
状态转移方程：f[j] = f[j] | f[j-v[第i个桶]；
目标状态：f[Q]

/*
ID: lorelei3
TASK: milk4
LANG: C++
*/

#include <fstream>
#include <algorithm>
#include <memory.h>

using namespace std;

const int MAXP = 105;
const int MAXQ = 20000;

int Q,P,v[MAXP]; 
int ans, use[MAXP];

ifstream fin("milk4.in");
ofstream fout("milk4.out");

void input(){
    fin>>Q;
    fin>>P;
    for(int i=1; i<=P; ++i)
        fin>>v[i];

    sort(v+1, v+1+P);
}

void output(){
    fout<<ans;
    for(int i=1; i<=ans; ++i)
        fout<<" "<<v[use[i]];
    fout<<endl;
    exit(0);
}

bool f[MAXQ];
void dp(){
    int i,j;
    memset(f, false, sizeof(f));
    for(i=1; i<=Q/v[use[1]]; ++i)
        f[i*v[use[1]]]=true;

    for(i=2; i<=ans; i++)
        for(j=v[use[i]]; j<=Q; ++j)
            f[j] |= f[j-v[use[i]]];

    if(f[Q])
        output();

}

void dfs(int k){
    for(int i=use[k-1]+1; i<=P-ans+k; ++i){
        use[k]=i;
        if(k==ans)
            dp();
        else
            dfs(k+1);
    }
}

void DFSID(){
    for(ans=1; ans<=P; ++ans)
        dfs(1);
}

int main(){
    input();
    DFSID();
    return 0;
}


posted on 2011-02-10 14:18 小阮 阅读(314) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮