题解

264 条题解

  • 10
    @ 2017-05-07 22:24:17
    /*
    好题~一个很巧妙的dp~
    我们看到因为是有n堆如果和n扯上关系状态很难表示
    那么我们可以这么想
    我们可以将n堆分别隔离开看作一个单独的个体
    然后对齐0/1背包必然可以求出每堆积木抽取若干积木之后
    可以达到的高度
    但是好像这也不太好处理 难道开一个二维数组分别记录下n堆的情况?
    这样太麻烦了
    我们可以换个角度想
    对于这n堆我们只需要求出他们公共可行部分~
    这样的话就转变了只要求出大家都可以达到哪些高度
    取最大的就好
    这样我们可以用一个f[]来记录每个高度是不是大家都是可行的
    对于每次推出的一个g[]表示第i个数组的每个高度的可行性
    我们都f[j]&=g[j]
    这样最后剩下的f[]如果是可行的
    那么必然是大家都共有的~
    这个思想很奇妙也很重要经常可能会用到
    这里我们的j的从0...sum
    sum应该是所有堆的高度总和的最小值
    这里我偷了个懒直接从0...10000(题目中100*100)
    这样虽然慢了一点但是就懒得储存h[]了
    (OTZ时间换空间23333)
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXV=11000;
    const int MAXN=105;
    bool f[MAXV],g[MAXV];
    int n;
    
    void init()
    {
        scanf("%d",&n);
    }
    
    void DP()
    {
        for(int i=0;i<=10000;i++)
            f[i]=1;
        for(int i=1;i<=n;i++)
        {
            memset(g,0,sizeof(g));  g[0]=1; int x=0;
            while(scanf("%d",&x)==1&&x!=-1)
            {
                for(int j=10000;j>=0;j--)
                    if(g[j])
                        g[j+x]=1;
            }
            for(int j=0;j<=10000;j++)
                f[j]&=g[j];
        }
        for(int j=10000;j>=0;j--)
            if(f[j])
            {
                printf("%d\n",j);
                return;
            }
    }
    
    int main()
    {
        init();
        DP();
    }
         
    
  • 1
    @ 2018-05-25 13:33:25
    
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    typedef long long A;
    const int W=11000;
    int main() {
        A g[W]= {0},n=0,f[W]= {0};
        cin>>n;
        for(int i=0;i<=W-1;i++)
        f[i]=1;
        for(A i=1; i<=n; i++) 
        {
            memset(g,0,sizeof(g));
            g[0]=1;
            int x=0;
            while(cin>>x&&x!=-1) 
            {
                for(int j=W-1; j>=0; j--)
                    if(g[j])
                    g[j+x]=1;
            }
            for(int j=0; j<=W-1; j++)
                f[j]&=g[j];
        }
        for(int j=10000; j>=0; j--) 
        {
            if(f[j]) 
            {
                cout<<j;
                return 0;
            }
        }
    }
    
    
  • 1
    @ 2017-10-07 14:47:38

    简单说一下我的思路 参考01背包
    每个城堡都做一遍 找出可以达到的高度
    之后再用数组&操作找出可以共同达到的高度
    之后从10000(城堡可能达到的最大高度)向下循环输出第一个可以共同达到的高度即可
    ps:由于无法完成要输出0,所以最后要确保0可以正常输出

    #include<bits/stdc++.h>
    using namespace std;
    int a;
    int f[10000],g[10000];//分别为记录共同可以达到的高度数组 和每个可以达到的高度数组 
    int main()
    {
        int n,i,j;//分别为城堡数量 和两个循环控制量 
        memset(f,1,sizeof(f)); //将共同数组初始值置为1 用于之后取与 
        cin>>n;
        for(i=1;i<=n;i++)//开始循环算每个城堡可以达到的高度 
        {
          memset(g,0,sizeof(g));//每次循环都要将数组初始化为0 写在前面 
          g[0]=1;//用于记录第一个可以到达的高度 
          while(cin>>a)//输入积木棱长 
          {
           if(a==-1) break;
           else for(j=10000;j>=0;j--)
            if(g[j]==1) g[j+a]=1;//j+a为该城堡可以到达的高度 
          }
          for(j=1;j<=10000;j++)
           f[j]&=g[j];//&的意义:1&1=1,1&0=0 用于求共同 
        }
        f[0]=1;//无法完成输出0 
        for(i=10000;i>=0;i--)
         if(f[i]==1)  {cout<<i;break;}
        
        return 0;     
    }
    
  • 0
    @ 2017-07-04 13:54:28

    n个城堡单独背包,记录可能的高度。

    #include<iostream>
    using namespace std;
    short n,max_hight,bh[101][101],bn[101];
    bool bag[101][10001]={0};
    int main()
    {
        cin>>n;
        for(short i=1;i<=n;i++)
        {
            short j=0;
            do{
                j++;
                short height;
                cin>>height;    
                if(height==-1)
                    break;
                else
                    bh[i][j]=height;
            }while(1);
            bn[i]=j-1;
        }
        for(short i=1;i<=n;i++)
            bag[i][0]=1;
        for(short i=1;i<=n;i++)
            for(short j=1;j<=bn[i];j++)
                for(short k=10000-bh[i][j];k>=0;k--)
                    if(bag[i][k]==1)
                        bag[i][k+bh[i][j]]=1;
        for(short i=10000;i>=0;i--)
        {
            bool judge=1;
            for(short j=1;j<=n;j++)
                if(bag[j][i]==0)
                {
                    judge=0;
                    break;
                }
            if(judge==1)
            {
                cout<<i;
                break;
            }
        }
        return 0;
    }
    
  • 0
    @ 2017-04-10 13:30:43

    还是 01 背包问题,相当于每个城堡都做一次,看看那个状态是每个城堡都能到达的。

    #include <cstdio>
    int N,w,ans,s[10005],f[105][10005];
    
    int main(){
        freopen("1.txt","r",stdin);
        for (int i=1; i<=100; i++) f[i][0]=1;
        scanf("%d",&N);
        for (int i=1; i<=N; i++)
            while ((scanf("%d",&w),w)!=-1)
                for (int j=10000; j>=w; j--) if (f[i][j-w] && !f[i][j]) s[j]+=f[i][j]=1;
        for (ans=10000; ans && s[ans]!=N; ans--);
        printf("%d",ans);
    }
    
  • 0
    @ 2016-08-29 21:44:17

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    bool judge[101][10004];
    int high[101][10004];
    int num[101];
    int main()
    {
    int n,maxn=-9999999;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    int sum=0;
    for(;;)
    {
    scanf("%d",&high[i][++num[i]]);
    if(high[i][num[i]]==-1)break;
    sum+=high[i][num[i]];
    }
    num[i]--;judge[i][0]=true;
    if(sum>=maxn)maxn=sum;
    judge[i][sum]=true;
    for(int j=1;j<=num[i];j++)
    {
    for(int k=sum;k>=0;k--)
    judge[i][k]=(judge[i][k]||judge[i][k-high[i][j]]);
    }
    }
    for(int i=maxn;i>=0;i--)
    {
    for(int j=1;j<=n;j++)
    {
    if(!judge[j][i])break;
    if(j==n)
    {
    printf("%d",i);return 0;
    }
    }
    }
    }

  • 0
    @ 2016-08-07 21:44:25

    练习位运算不错
    ```
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <bitset>
    #define rep(x,to) for(int x=0;x<(to);x++)
    #define repn(x,to) for(int x=1;x<=(to);x++)
    using namespace std;
    const int mod=1e9+7;
    bitset<10005> bs[105];
    int main()
    {
    #ifdef LOCAL
    freopen("in","r",stdin);
    #endif // LOCAL
    int n,x,ans=0;
    scanf("%d",&n);
    rep(i,n)
    {
    bs[i][0]=1;
    for(;;)
    {
    scanf("%d",&x);
    //cout<<x<<endl;
    if(x==-1)break;
    bs[i]|=bs[i]<<x;
    }
    }
    //rep(i,n)cout<<bs[i]<<endl;
    repn(i,n)bs[i]&=bs[i-1];
    rep(i,(int)bs[n-1].size())if(bs[n-1][i])ans=max(ans,i);
    //cout<<bs[0]<<endl;
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2016-04-30 07:49:11
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    int n;
    bool f[10010] = {0}, f2[10010] = {0};
    
    int main ()
    {
        //freopen ("in.txt", "r", stdin);
        cin >> n;
        memset (f, true, sizeof(f));
        for (int i = 0; i < n; i++) {
            memset (f2, false, sizeof(f2));
            f2[0] = true;
            int e = 0;
            while (cin >> e && e != -1) {
                for (int j = 10000; j >= 0; j--) {
                    if (f2[j]) f2[j + e] = true;
                }
            }
            for (int j = 0; j <= 10000; j++) {
                f[j] = f[j] && f2[j];
            }   
        }
        for (int i = 10000; i >= 0; i--) 
            if (f[i]) { cout << i; break;}
        return 0;
    }
    
  • 0
    @ 2016-04-15 12:21:06

    #include<cstdio>
    int f[10001],g[10001],n,h;
    int main()
    {
    scanf("%d",&n);
    memset(f,true,sizeof(f));
    while(n--)
    {
    g[0]=true;
    for(int i=1;i<=10000;++i)
    g[i]=false;
    for(scanf("%d",&h);h>-1;scanf("%d",&h))
    for(int i=10000;i>=h;--i)
    g[i]|=g[i-h];
    for(int i=0;i<=10000;++i)
    f[i]&=g[i];
    }
    for(int i=10000;i>=0;--i)
    if(f[i]){printf("%d\n",i);break;}
    return 0;
    }

  • 0
    @ 2015-05-11 16:39:33

    #include <iostream>
    #include <cstring>

    using namespace std;

    int a[6005];
    int b[6005];
    int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
    int js;
    memset(b, 0, sizeof(b));
    b[0] = 1;
    while(cin >> js){
    if(js == -1) break;
    for(int i = 6000; i >= 0; --i){
    if(b[i] == 1){
    b[i + js] = 1;
    }
    }
    }
    for(int i = 0; i <= 6000; ++i){
    a[i] += b[i];
    }
    }
    for(int i = 6000; i >= 0; --i){
    if(a[i] == n){
    cout << i << endl;
    break;
    }
    }
    }

  • 0
    @ 2014-07-11 16:31:31

    #include<cstdio>
    #include<memory.h>
    const int maxsize=10001;
    int n;
    bool ac[maxsize]={true},ac2[maxsize]={true},firsttime=true;
    int main(){
    scanf("%d\n",&n);
    memset(ac,true,sizeof(ac));
    for(int i=0;i<n;i++){
    memset(ac2,false,sizeof(ac2));
    ac2[0]=true;
    int tmp=0;
    while(scanf("%d ",&tmp)!=EOF&&tmp!=-1){
    for(int j=maxsize-1;j>=0;j--){
    if(ac2[j]){
    ac2[j+tmp]=true;
    }else;
    }
    }
    for(int j=maxsize-1;j>=0;j--){
    ac[j]=ac[j]&&ac2[j];
    }
    }
    for(int i=maxsize-1;i>=0;i--){
    if(ac[i]){
    printf("%d\n",i);return 0;
    }
    }
    }
    01背包水题

  • 0
    @ 2013-08-23 21:00:49

    话说积木不用排序也AC?艹

  • 0
    @ 2013-08-15 23:00:01

    #include <iostream>
    #include <climits>
    using namespace std;

    int h[102][102],len[102]={0};
    bool F[102][10002]={};

    int main()
    {
    int N;
    cin >> N;

    int S_min=INT_MAX;
    for(int i=1;i<=N;++i)
    {
    int S=0;
    while(true)
    {
    cin >> h[i][++len[i]];
    if(h[i][len[i]]==-1)
    break;
    else S+=h[i][len[i]];
    }
    --len[i];
    if(S<S_min)
    S_min=S;
    }

    for(int t=1;t<=N;++t)
    {
    F[t][0]=true;
    for(int i=1;i<=len[t];++i)
    for(int j=S_min;j>=h[t][i];--j)
    if(F[t][j-h[t][i]])
    F[t][j]=F[t][j-h[t][i]];
    }

    for(int i=S_min;i>=0;--i)
    {
    bool OK=true;
    for(int t=1;t<=N;++t)
    {
    OK=OK&&F[t][i];
    if(!OK)
    break;
    }
    if(OK)
    {
    cout << i << endl;
    //system("pause");
    return 0;
    }
    }
    return 0;
    }

    我好粗心,第一次提交忘了初始化S_min了,第二次提交数组开小了。

  • 0
    @ 2013-03-20 20:45:41

    /*
    description: 有n堆积木,每堆由一定数目(<=100)的个积木堆成,每个积木的高度少于100。
    现在让你从这n堆积木中抽出一些积木,使得这n堆积木的高度一样,且同时使得高度最大。
    solution: 对每一堆积木进行背包,标记每个可以达到的高度,然后找出最大的同时都能达到的高度即可。
    author:uncleFun
    */
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <cstdio>
    #define MAXN 102
    using namespace std ;

    int n, min_h ;
    int b[MAXN][MAXN], ct[MAXN*MAXN], sum[MAXN][MAXN] ;
    bool m[MAXN*MAXN] ;
    queue<int> que ;

    void zn_Pack(int k) //01背包
    {
    int i, j, h, num = b[k][0] ;
    memset(m, 0, sizeof(m)) ;
    while(!que.empty()) que.pop() ;
    que.push(0) ; m[0] = 1 ;
    for(i = 1 ; i <= num ; i ++)
    {
    while(!que.empty())
    {
    h = que.front() ; que.pop() ;
    if(!m[h+b[k][i]]) m[h+b[k][i]] = 1 ;
    }
    if(i == num) break ;
    for(j = 0 ; j <= sum[k][num] ; j ++)
    if(m[j]) que.push(j) ;
    }
    }

    int solve()
    {
    int i, j ;
    memset(ct, 0, sizeof(ct)) ;
    for(i = 1 ; i <= n ; i ++)
    {
    zn_Pack(i) ;
    for(j = 0 ; j <= sum[i][b[i][0]] ; j ++) if(m[j]) ct[j] ++ ;
    }
    for(i = sum[n][b[n][0]] ; i && (ct[i]!= n) ; i -- ) ;
    return i ;
    }

    int main()
    {
    int i, j, h ;
    while (~scanf("%d", &n))
    {
    while(!que.empty()) que.pop() ;
    for(i = 1 ; i <= n ; i ++)
    {
    j = sum[i][0] = 0 ;
    scanf("%d", &h) ;
    while (h != -1)
    {

    b[i][++j] = h ;
    sum[i][j] = sum[i][j-1] + h ;
    scanf("%d", &h) ;

    }
    if(j == 0) continue ;
    b[i][0] = j ;
    }
    printf("%d\n", solve()) ;
    }
    return 0 ;
    }

  • 0
    @ 2012-11-04 22:20:05

    01背包

    ├ 测试数据 01:答案正确... (0ms, 8308KB)

    ├ 测试数据 02:答案正确... (0ms, 8308KB)

    ├ 测试数据 03:答案正确... (0ms, 8308KB)

    ├ 测试数据 04:答案正确... (0ms, 8308KB)

    ├ 测试数据 05:答案正确... (0ms, 8308KB)

    ├ 测试数据 06:答案正确... (0ms, 8308KB)

    ├ 测试数据 07:答案正确... (0ms, 8308KB)

    ├ 测试数据 08:答案正确... (0ms, 8308KB)

    ├ 测试数据 09:答案正确... (0ms, 8308KB)

    ├ 测试数据 10:答案正确... (12ms, 8308KB)

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

    Accepted / 100 / 12ms / 8308KB

  • 0
    @ 2012-10-27 13:35:20

    VijosNT Mini 2.0.5.7 Special for Vijos 

    编译通过... 

    ├ 测试数据 01:答案正确... (0ms, 1596KB) 

    ├ 测试数据 02:答案正确... (0ms, 1596KB) 

    ├ 测试数据 03:答案正确... (0ms, 1596KB) 

    ├ 测试数据 04:答案正确... (0ms, 1596KB) 

    ├ 测试数据 05:答案正确... (0ms, 1596KB) 

    ├ 测试数据 06:答案正确... (0ms, 1596KB) 

    ├ 测试数据 07:答案正确... (0ms, 1596KB) 

    ├ 测试数据 08:答案正确... (0ms, 1596KB) 

    ├ 测试数据 09:答案正确... (0ms, 1596KB) 

    ├ 测试数据 10:答案正确... (0ms, 1596KB)

    用递推,每座塔分别处理,暴力就过了。。。

  • 0
    @ 2012-08-13 10:30:19

    o(n^3)也可以秒杀。。。囧。

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 272KB)

    ├ 测试数据 02:答案正确... (0ms, 272KB)

    ├ 测试数据 03:答案正确... (0ms, 272KB)

    ├ 测试数据 04:答案正确... (0ms, 272KB)

    ├ 测试数据 05:答案正确... (0ms, 272KB)

    ├ 测试数据 06:答案正确... (0ms, 272KB)

    ├ 测试数据 07:答案正确... (0ms, 272KB)

    ├ 测试数据 08:答案正确... (0ms, 272KB)

    ├ 测试数据 09:答案正确... (0ms, 272KB)

    ├ 测试数据 10:答案正确... (0ms, 272KB)

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

    Accepted / 100 / 0ms / 272KB

  • 0
    @ 2012-07-26 00:15:46

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    直接裸背包就可以过。stl的set小数据有优势,

    大数据的时候,基本上10000个点每个都访问了。

    所以直接变成10000*lg10000=4倍时间

    然后stl速度大家懂的,就会T了。

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    int n;

    int dp[100][11004];

    int dd[104][104];

    int cnt[10004];

    int sum;

    void solve(){

    int tv;

    int pos;

    sum = 0;

    memset(dp,0,sizeof(dp));

    memset(cnt,0,sizeof(cnt));

    for (int i = 0; i < n; i++)

    {

    dp[i][0] = 1;

    for (int j = 1; j = 0; k--)

    if (dp[i][k])

    dp[i][k + dd[i][j]] = 1;

    }

    for (int j = 0; j

信息

ID
1059
难度
6
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
7392
已通过
2249
通过率
30%
被复制
3
上传者