题解 - Vijos

13

/*
好题~一个很巧妙的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();
}

4

mufeng LV 7 @ 7 年前

简单说一下我的思路参考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;     
}

gxygxy @ 4 年前

谢谢你的代码和详解！谢谢！

1

Elucidator LV 7 @ 6 年前


#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

hehepig LV 7 @ 8 年前

还是 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

j18tm01 LV 10 @ 4 年前

#include <cstdio>
#include <cstring>
int n, m, h[105], f[10005], c[10005], i, j, k;
int main(){
    scanf("%d", &n);
    for(k=1; k<=n; k++){
        m = 1;
        scanf("%d", &h[m]);
        while(h[m] != -1) scanf("%d", &h[++m]);
        memset(f, 0, sizeof(f));
        for(f[0]=i=1; i<m; i++){
            for(j=10000; j>=h[i]; j--){
                f[j] |= f[j-h[i]];
            }
        }
        for(i=1; i<=10000; i++) c[i] += f[i];
    }
    for(i=10000; i>=1; i--) if(c[i] == n) break;
    printf("%d\n", i);
    return 0;
}

0

qiuzili LV 8 @ 7 年前

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

937337156 LV 8 @ 8 年前

C++代码+题解
http://www.cnblogs.com/937337156Zhang/p/6044313.html

0

cdqzgxxqdql LV 10 @ 8 年前

#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

iKyrre LV 8 @ 8 年前

练习位运算不错
```
#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

caesar_199 LV 9 @ 8 年前

#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

846047746 LV 8 @ 8 年前

#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

whyfrank LV 8 @ 9 年前

#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

Curt_Xu LV 8 @ 10 年前

#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

一方T行 LV 10 @ 11 年前

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

0

帝皇法老 LV 7 @ 11 年前

#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

uncleFun LV 8 @ 12 年前

/*
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

SEX丶Elope LV 6 @ 12 年前

点击查看程序源码+详细题解

0

kimo LV 8 @ 12 年前

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

Dungeon LV 8 @ 12 年前

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

330459659 LV 10 @ 12 年前

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

题解

265 条题解

积木城堡

信息

状态

开发

支持

题解

265 条题解

积木城堡

信息

状态

开发

支持

还没有账户？

登录