M_sea

洛谷1441 砝码称重
Luogu分析先枚举所有去掉的情况,再用可行性DP统计。前面那一部分可以枚举二进制状态,1的个数正好为$n-m$就...
扫描右侧二维码阅读全文
25
2018/11

洛谷1441 砝码称重

Luogu

分析

先枚举所有去掉的情况,再用可行性DP统计。

前面那一部分可以枚举二进制状态,1的个数正好为$n-m$就是合法状态。

后面那一部分可以用bitset搞。这个方法很巧妙,比我货币系统那个题写的丑的死的可行性DP不知道高到哪去了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,m,ans=0;
int a[30];

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int S=0;S<(1<<n);++S) {
        if (__builtin_popcount(S)!=n-m) continue;
        bitset<2010> qwq;
        qwq[0]=1;
        for (re int i=1;i<=n;++i)
            if (S&(1<<(i-1))) qwq|=(qwq<<a[i]);
        ans=max(ans,(int)qwq.count()-1); //0不算
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 20 PM

发表评论

2 条评论

  1. smy

    太暴力了

    1. M_sea
      @smy

      bitset吼啊qwq