53 条题解

  • 2
    @ 2018-02-13 15:13:09

    同USACO5.3 Milk Measuring
    观察数据范围,我们就想到了dfs,而由于题目要求桶数尽量小,很明显可以用迭代加深限制层数求解。
    那么,大致思路就是:枚举桶的方案——判断是否可行——可行退出,输出答案。
    枚举部分毫无疑问的dfs。判断部分用完全背包。这样就解决了此题。
    C++代码:

    #include<cstdio>
    #include<cctype>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    inline int rd(){
        char c=getchar();
        while(!isdigit(c))c=getchar();
        int x=c-48;
        for(c=getchar();isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-48;
        return x;
    }
    short buf[10];
    inline void wt(int x){
        int l=-1;
        while(x>9){
            buf[++l]=x%10;
            x/=10;
        }
        putchar(x+48);
        while(l>=0)putchar(buf[l--]+48);
    }  //IO优化,卡常数
    int a[105],st[105],l=-1,q,n;  //st是栈,l是栈顶指针
    bool f[20005];  //dp用
    bool dp(){
        int i,j;
        memset(f,0,sizeof(f));
        f[0]=1;
        for(i=0;i<=l;i++){
            for(j=st[i];j<=q;j++)if(f[j-st[i]])f[j]=1;  //完全背包
            if(f[q])return 1;  //小优化:可以让速度加快很多
        }
        return 0;
    }
    bool dfs(int h,int maxh){
        if(l==maxh-1)return dp();
        if(h==n-1){
            if(dp())return 1;
            st[++l]=a[h];
            if(dp())return 1;
            l--;
            return 0;
        }  //递归边界单独处理
        st[++l]=a[h];
        if(dp()||dfs(h+1,maxh))return 1;
        l--;
        return dfs(h+1,maxh);  //分情况
    }
    int main(){
        int i;
        q=rd();n=rd();
        for(i=0;i<n;i++)a[i]=rd();
        sort(a,a+n);  //题目没说桶是排好序的,加了保险
        for(i=1;;i++)if(dfs(0,i))break;  //迭代加深
        wt(l+1);
        for(i=0;i<=l;i++){
            putchar(' ');
            wt(st[i]);
        }
        return 0;
    }
    
    

    PS.此题也可以全用dp,记f(i,j)为用前i个桶拼出j的容量的最小桶数,当作完全背包求解。速度比dfs快,但打印方案比较困难。

  • 1
    @ 2018-02-28 14:21:35

    看这里看这里!非爆搜呦~
    先dp一次算最小需要的桶数
    然后根据桶数记忆化搜索
    93ms

    #include <bits/stdc++.h>
    using namespace std;
    using LL = long long;
    #define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
    #define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
    #define mem(f,x) memset(f,x,sizeof(f))
    //========================================================================
    int f[20005];
    int c[105];
    int v[20005];
    int link[20005];
    int n, m;
    int cmp(int A, int a, int B, int b) {
        if (a == 0 || b == 0) {
            if (v[A] < v[B]) return 1;
            if (v[A] > v[B]) return -1;
            return 0;
        }
        int temp = cmp(a, link[a], b, link[b]);
        if (temp == 0) {
            if (v[A - a] < v[B - b]) return 1;
            if (v[A - a] > v[B - b]) return -1;
            return 0;
        }
        else {
            return temp;
        }
    }
    void dfs(int x, int y) {
        if (link[x] != -1) return;
        if (y == 1) {
            link[x] = 0;
            return;
        }
        FORD(i, x - 1, 1) {
            if (f[i] == y - 1) {
                if (v[x - i] == -1) continue;
                dfs(i, y - 1);
                if (link[x] == -1) {
                    link[x] = i;
                }
                else {
                    if (cmp(x, i, x, link[x]) > 0)
                        link[x] = i;
                }
            }
        }
    }
    int main()
    {
        cin >> m >> n;
        FOR(i, 1, n) cin >> c[i];
        FOR(k, 1, n - 1) {
            FOR(j, 1, n - k) {
                if (c[j] > c[j + 1]) {
                    int t = c[j];
                    c[j] = c[j + 1];
                    c[j + 1] = t;
                }
            }
        }
        mem(f, 0x7f);
        f[0] = 0;
        FOR(k, 1, n) {
            int minx;
            int j;
            FOR(i, 0, c[k] - 1) {
                j = i + c[k];
                minx = f[i] + 1;
                while (j <= m) {
                    if (f[j] + 1 < minx) {
                        minx = f[j] + 1;
                    }
                    else {
                        f[j] = min(f[j], minx);
                    }
                    j += c[k];
                }
            }
        }
        cout << f[m] << " ";
        mem(v, -1);
        FOR(k, 1, n) {
            FOR(i, 1, m) {
                if (v[i] != -1) continue;
                if ((i%c[k]) == 0) v[i] = k;
            }
        }
        mem(link, -1);
        dfs(m, f[m]);
        vector<int> ans = {};
        int tmpm = m;
        while (link[tmpm] != 0) {
            ans.push_back(v[tmpm - link[tmpm]]);
            tmpm = link[tmpm];
        }
        ans.push_back(v[tmpm]);
        FORD(i, (int)ans.size() - 1, 1)
            cout << c[ans[i]] << " ";
        cout << c[ans[0]];
        return 0;
    }
    
  • 1
    @ 2017-05-08 12:29:03
    /*
    USACO的一道题目改了个背景~好题
    搜索+背包dp~
    我们看到我们根本很难去搜索
    如果去枚举选取哪些再判断可行的话
    那么我们会有2^100种情况检查
    必然是会爆炸的~
    这样我们其实可以采用迭代加深搜索的方法
    这样完全是可行的
    因为这样完全可以减少一些使用了全部水桶的方案
    只要找到一个解就退出也是挺快的
    即我们从1...n枚举最大深度上线maxd
    然后再枚举选取这maxd个元素~这里用dfs来解决
    选取好后开始检查这maxd个元素是否可以填满V容量
    这像不像是背包?
    因为每个水桶可以用无限多次
    所以我们可以用完全背包来解决
    因为只需要判断是否能装满所以我们用f[]的0或1来表示能否到达
    然后完全背包刷一遍即可
    这里可以用递推地方法也可以用递归的方法~
    窝两个都写了一下
    递归会比递推快很多~因为递推要全部刷一遍复杂度是O(nV)的
    而递归递归下去找到一个可行解就是连续递归返回
    所以效率高了很多(220ms-45ms)
    这样就可以解决这道题了~
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=105;
    const int MAXV=21000;
    int f[MAXV];
    int a[MAXN];
    int v[MAXN];
    int V,n;
    int maxd;
    
    void init()
    {
        scanf("%d%d",&V,&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i]);
    }
    
    void print()
    {
        printf("%d ",maxd);
        for(int i=1;i<=maxd;i++)
            printf("%d ",a[i]);
        exit(0);
    }
    
    /*bool check(int& V)
    {
        memset(f,0,sizeof(f));  f[0]=1;
        for(int i=1;i<=maxd;i++)
            for(int j=0;j<=V;j++)
                if(f[j]&&j+a[i]<=V)
                    f[j+a[i]]=1;
        return f[V];
    }*/
    
    bool check(int x)
    {
        int &s=f[x];
        if(s!=-1)
            return s;
        if(x==0)
            return s=1;
        for(int i=1;i<=maxd;i++)
            if(x>=a[i]&&check(x-a[i]))//第一次进入是从此入口递归下降
                return s=1;
        return s=0;
    }
    
    void dfs(int depth,int k)//当前在选第cur个位置,到了第k个水桶
    {
        if(depth==maxd+1)
        {
            memset(f,-1,sizeof(f));
            if(check(V))
                print();
            return;
        }
        if(k>n)
            return;
        a[depth]=v[k];
        dfs(depth+1,k+1);//选了了该水桶
        dfs(depth,k+1);//没选该水桶(巧妙利用了覆盖)
    }
    
    void id_dfs()
    {
        sort(v+1,v+n+1);
        n=unique(v+1,v+n+1)-v-1;//优化程度不大(数据重合少)
        for(maxd=1;maxd<=n;maxd++)
            dfs(1,1);
    }
    
    int main()
    {
        init();
        id_dfs();
    }
         
    
  • 0
    @ 2020-01-24 15:03:16

    因为是一道 迭代加深搜索 ,所以没什么可说的。

    普及一下: 迭代加深搜索 是\(dfs\)和\(bfs\)的结合体,其搜索方法为:

    每次规定一个搜索深度\(d\),让\(dfs\)在\(d\)层之内搜索。

    然后不断增大\(d\),知道答案不符合为止。

    而本题恰好符合两个条件:深度不确定、状态巨大。

    所以\(dfs\)和\(bfs\)都无法满足喽!

    \(d\)表示用桶的个数。

    //迭代加深搜索 
    #pragma GCC optimize(2)
    #include<bits/stdc++.h>
    using namespace std;
    
    inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
        int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
    
    int n,m,a[110];
    int d;
    int q[110];
    bool f[21000];
    inline bool check(){
        for(int i=1;i<=m;i++) f[i]=false;
        f[0]=true;
        for(int i=1;i<=d;i++)
        for(int j=0;j+q[i]<=m;j++) f[j+q[i]]|=f[j];
            //背包写法 O(m)
        return f[m];     
    }
    inline bool dfs(int x,int y) {
        //从y到n选
        //让桶的大小递增 
        if(x>d) return check(); 
        for(int i=y;i<=n;i++) {
            q[x]=a[i];
            if(dfs(x+1,i+1)) return true;
        } return false;
    }
    
    int main(){
        m=read(),n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        sort(a+1,a+1+n);
        for(d=1;;d++)
            if(dfs(1,1)) break;
        printf("%d ",d);
        for(int i=1;i<=d;i++) printf("%d ",q[i]);
        putchar('\n');  
        return 0;
    }
    
    
  • 0
    @ 2016-08-21 11:21:23
    //Discribe:
    /*
    dfs+dp 
    */
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <ctime>
    #include <cctype>
    #include <climits>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <vector>
    #include <string>
    #include <cstring>
    using namespace std;
    int p,q;
    int useNum=0;
    int num[105]={0},dp[20005]={0},ans[105]={0};
    
    bool can(int left)//剩余left容量能否倒满 
    {
        if (dp[left] != -1)//已经确定 
            return dp[left];
        if (left == 0)//倒满了 
            return dp[left] = 1;
        for (int i = 0; i < useNum; i++)//枚举每一个桶 
            if (left >= ans[i] && can(left - ans[i]))//桶还能倒水,继续 
                return dp[left] = 1;
        return dp[left] = 0;
    }
    
    void dfs(int total, int now)//total:现在第几个桶。now:已经放了几个桶 
    {
        if (now == useNum)//放完了 
        {
            memset(dp, -1, sizeof dp);//初始化 
            if (can(q))
            {
                printf("%d", useNum);//输出桶数 
                for (int i = 0; i < now; i++)
                    printf(" %d", ans[i]);
                puts("");
                exit(0);//退出整个程序 
            }
            return;
        }
        if (total >= p)//边界 
            return;
        ans[now] = num[total];//记录答案 
        dfs(total + 1, now + 1);//买这个桶 
        dfs(total + 1, now);//不买这个桶
        //前面两行顺序不能颠倒!!! 
    }
    int main()
    {
        //freopen("water.in","r",stdin);
        //freopen("water.out","w",stdout);
        scanf("%d%d",&q,&p);
        for (int i=0;i<p;i++) {
            scanf("%d",&num[i]);
        }
        sort(num,num+p);//排序 
        for (useNum=1;useNum<=p;useNum++) {//枚举使用桶数 
            dfs(0,0);//dfs一发 
        }
        return 0;
    }
    
    
    
  • 0
    @ 2016-08-21 11:17:04
    //不加注释的代码都是耍流氓
    #include <iostream>
    #include <cctype>
    #include <climits>
    #include <stack>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    #define N 1001
    #define M 20001
    int a[N]={0},k,q,p,ans[N]={0};
    int f[M];
    bool can(int n)
    {
        int &zz=f[n];
        if(n==0)
            return zz=1;
        if(zz>=0)//记忆化搜索
            return zz;
        for(int i=1;i<=k;i++)
            if(n>=ans[i]&&can(n-ans[i]))
                return zz=1;
        return zz=0;
    }
    void dfs(int n,int m)//n表示做到多少 m表示第几个桶
    {
        if(m==k+1)//全部做完了
        {
            memset(f,-1,sizeof(f));
            if(can(q))//如果容积q可以的话
            {
                cout<<k<<" ";
                for(int i=1;i<m;i++)
                    cout<<ans[i]<<" ";
                cout<<endl;
                exit(0);//完全结束
            }
            return ;//这个return很重要
        }
        if(n>p)//递归边界
            return ;
        ans[m]=a[n];
        dfs(n+1,m+1);//选第m个桶
        dfs(n+1,m);//不选第m个桶
    }
    int main()
    {
        cin>>q>>p;
        for(int i=1;i<=p;i++)
            cin>>a[i];
        sort(a+1,a+p+1);
        for(k=1;k<=p;k++)//枚举K个桶的情况
            dfs(1,1);
    }
    
  • 0
    @ 2014-08-21 22:04:57
    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int VMAXN = 2e4 + 10;
    const int TMAXN = 100 + 10;
    const int INF = 0x3f3f3f3f;
     
    int num[TMAXN], dp[VMAXN], k, n, m;
    int ans[TMAXN];
     
    bool Check(int sum)
    {
        int &cur = dp[sum];
        if (cur != -1)
            return cur;
        if (sum == 0)
            return cur = 1;
        for (int i = 0; i < k; i++)
            if (sum >= ans[i] && Check(sum - ans[i]))
                return cur = 1;
        return cur = 0;
    }
     
    void DFSID(int cur, int dep)
    {
        if (dep == k)
        {
            memset(dp, -1, sizeof dp);
            if (Check(n))
            {
                printf("%d", k);
                for (int i = 0; i < dep; i++)
                    printf(" %d", ans[i]);
                puts("");
                exit(0);
            }
            return;
        }
        if (cur >= m)
            return;
        ans[dep] = num[cur];
        DFSID(cur + 1, dep + 1);
        DFSID(cur + 1, dep);
    }
     
    int main()
    {
        //freopen("input.txt", "r", stdin);
        int i, j;
        scanf("%d%d", &n, &m);
        for (i = 0; i < m; i++)
            scanf("%d", &num[i]);
        sort(num, num + m);
        for (k = 1; k <= m; k++)
            DFSID(0, 0);
        return 0;
    }
    
  • 0
    @ 2014-08-07 09:45:29

    这题太·········

  • 0
    @ 2013-10-17 20:32:38

    刚开始是在想不通为什么一个很烂的dfs+dp会秒杀。。
    后来才知道,输入的数据是不水的,但是输出的答案是很水的
    导致你在搜索长度为3的序列时就会得到答案。
    首先按照长度,搜索出所有满足的序列,然后把这个序列扔到dp里,有答案就直接halt。
    思路还是比较的清晰,但我想不是正解,因为如果不是因为数据水,肯定不会秒杀
    如果哪位大牛,有详细思路,或者有一些其他看法欢迎+我QQ841249284
    大家一起搞竞赛!
    DXE-SYF

  • 0
    @ 2012-10-13 21:25:32

    额,DFSID+DP竟然0ms,不过这个应该很好卡吧!随便设计个数据就会卡

  • 0
    @ 2009-11-08 12:26:28

    靠,题目都看不懂,什么意思啊

  • 0
    @ 2009-11-06 12:24:34
  • 0
    @ 2009-10-26 20:51:21

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    昔日多少次的提交,才换来如今的AC!

    这个我没有搜索,而是分两步做的。第一步显然背包就行了。这里我们求出了每个点的最少需要的桶的种类数。然后我们进行枚举。

    预处理can[i]表示能用一个桶装满容量为i的容器的最小桶编号。比如有桶容量分别是2,3,那么装满容量为6的容器的最小桶编号为1,所以can[6]=1

    假如我们第一步背包的结果保存在数组DP中,dp[i]表示i容量的缸所需最少桶数。

    接下来开两个数组记录符合条件的转移值。一开始数组1中只有一个元素m,然后枚举所有dp值为dp[m]-1的元素,不妨设为a1..ak,那么我们取t=min{can[m-ai],1

  • 0
    @ 2009-10-08 21:45:30

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 25ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 275ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 134ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 134ms

    恩,我感到十分自豪。

    大家都用搜索。我用Dp哈。

    时间复杂度为p*q*p*q/p;

    理论上讲是20000*20000*100;

    but它过了。

    只能说数据太弱了。

    完全背包不能用n*c的要用n*c*c/n的否则会破坏字典序。

    代码如下:

    type node=set of 1..100;

    var f:array[0..20000]of longint;

    num:array[0..20000]of node;

    a:array[1..100]of longint;

    p,q,i,j,t,k:longint;

    function pd(a,b:node):boolean;

    var i:longint;

    begin

    for i:=1 to 100 do

    begin

    if (i in a) and not (i in b) then exit(true);

    if not (i in a)and (i in b) then exit(false);

    end;

    end;

    begin

    assign(input,'vj1159.in');reset(input);

    assign(output,'vj1159.out');rewrite(output);

    readln(q);

    for i:=1 to q do f[i]:=maxlongint div 2;

    readln(p);

    for i:=1 to p do

    read(a[i]);

    for i:=1 to p do

    for j:=i+1 to p do

    if a[i]>a[j] then

    begin

    t:=a[i];a[i]:=a[j];a[j]:=t;

    end;

    for i:=1 to p do

    for j:=1 to q do

    for k:=1 to j div a[i] do

    if j-a[i]*k>=0 then

    if i in num[j-a[i]*k] then

    begin

    if f[j-a[i]*k]=f[j] then

    begin

    if pd(num[j-a[i]*k],num[j]) then

    begin

    num[j]:=num[j-a[i]*k];

    end;

    end

    else

    if f[j-a[i]*k]

  • 0
    @ 2009-10-05 16:55:19

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 56ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 291ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:347ms

    N次AC 我低级了。

  • 0
    @ 2009-10-05 16:31:23

    两次AC。。。。。

    DFSID真是快啊

    注意:没加DP呵。。。。。

    可惜第一次交忘了加快排了,竟然90分

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 150ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:150ms

    加了之后:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:72ms

    方法不讲了,详见程序:

    program vijos_1159;

    const

    maxN=100;

    maxM=20000;

    type

    TAns=array[1..maxM] of longint;

    var

    m,n:longint;

    a:array[1..maxN] of longint;

    ansDeep:longint;

    getAns:boolean;

    ans,tmp:TAns;

    temp:longint;

    procedure qSort(l,r:longint);

    var

    i,j,x:longint;

    begin

    i:=l;

    j:=r;

    x:=a[(i+j)>>1];

    repeat

    while a[i]x do dec(j);

    if ij;

    if il then qSort(l,j);

    end;

    procedure init;

    var

    i:longint;

    begin

    readln(m);

    readln(n);

    for i:=1 to n do

    readln(a[i]);

    qSort(1,n);

    end;

    function better(t:TAns):boolean;

    var

    i:longint;

    begin

    for i:=1 to ansDeep do begin

    if ans[i]t[i] then exit(true);

    end;

    exit(false);

    end;

    procedure ID(deep,weight,i:longint);

    var

    w:longint;

    begin

    if deep=ansDeep then begin

    if weight=m then begin

    if not getAns then ans:=tmp

    else if better(tmp) then ans:=tmp;

    getAns:=true;

    end;

    exit;

    end;

    if i=n+1 then exit;

    ID(deep,weight,i+1);

    w:=weight+a[i];

    if w>m then exit;

    tmp[deep+1]:=a[i];

    while w

  • 0
    @ 2009-10-03 14:02:27

    想不通列,,,,为什么纯dp不行啊。。。。哪里有后向性、?哪位大牛能给沙茶我解释下么。。。?

  • 0
    @ 2009-09-12 10:52:27

    同一个程序,一个90,一个AC,BS评测机。

  • 0
    @ 2009-09-11 00:02:25

    第一问DP不用说,第二问考虑使用ID-DFS(用DP比较麻烦,比较决策需要比较序列的字典序),也就是设置一个上限max,不断放大max,然后DFS找出可行的最优方案中,前max个桶中字典序最小的桶。这样搜的好处是放大的时候利于剪枝。

  • 0
    @ 2009-08-18 21:12:33

    搜索+DP~~

    不过想像各位大牛一样秒杀应该怎么做呢?

信息

ID
1159
难度
7
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
1972
已通过
440
通过率
22%
被复制
3
上传者