0%

Project1441砝码称重项目报告

摘要:搜索出状态后背包求解

P1441 砝码称重

题面

题目分析

那个…我的思路貌似很毒瘤.

先用搜索搜出要删去的数,压到一个二进制串中,利用物竞神仙同桌的$fx991$算出$C^{4}_{20}$只有4845,可以接受.

每搜到一个串后,跑一遍背包,背包的思路类似于noip2018 d1t2货币系统,用$01$背包先算出剩下的数能够组合出来的数,然后统计一遍所有能够组合出来的数,记录下统计的最大值即可.

代码也很好实现.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include "iostream"
#include "algorithm"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "map"
#include "queue"
#include "set"
#include "stack"
#include "vector"
#include "time.h"

#define lxl long long
#define R register
#define INF 2147483647
#define debug(x) printf("debug:%lld\n",x)

using namespace std;

lxl n,m,cnt,sec,ans,tot;
lxl a[21],f[20010];

inline lxl read(){char c=getchar();lxl f=1,output=0;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())output=(output<<1)+(output<<3)+c-'0';return output*f;}
//"必须熟练掌握压行技巧"
inline void dp()
{
cnt=0;
memset(f,-0x3f,sizeof(f));
f[0]=0;
for(R lxl i=1;i<=n;++i)
{
if(sec&(1<<i))continue;//暴力判断这个数有没有被删掉
for(R lxl j=tot;j>=a[i];j--)f[j]=max(f[j],f[j-a[i]]+1);//01背包,注意倒序枚举
}
for(R lxl i=1;i<=tot;++i)if(f[i]>0)cnt++;//如果这个数能够被剩下的数组合出来,累加答案
}
inline void work(lxl now,lxl pick)
{
if(pick==m)
{
dp();
ans=max(ans,cnt);
return;
}
for(R lxl i=now+1;i<=n;++i)
{
sec|=1<<i;//把这个位置置为1
work(i,pick+1);
sec&=(~(1<<i));//去掉这个位置上的1
}
}

signed main(void)
{
n=read(),m=read();
for(R lxl i=1;i<=n;++i)a[i]=read(),tot+=a[i];
work(0,0);
printf("%lld\n",ans);
return 0;
}