提供一种全新的做法，时空均优于目前的其他做法，码量也很小。最优解被打表抢了，好难受。
由于 $\log 10^8 < 27,\log 24 < 5$，因此可以用一个 unsigned int 把其他题解里两个数据拼起来，同时排序也自带第一二关键字，最重要的是空间仅为正常做法的一半。
而且由于两个数据是关联的，内存连续性能让其速度更进一步，不必写结构体。
提交记录
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
63
|
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
constexpr uint INF=0xffffffff;
int a[25],c[105];
uint dp[1<<24];
void out(){
puts("NIE");
exit(0);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
long long suma=0;
for(int i=0;i<n;i++){
scanf("%d",a+i);
suma+=a[i];
}
for(int i=0;i<m;i++)scanf("%d",c+i);
sort(c,c+m,greater<int>());
int actualm=min(n,m);
long long sumc=0;
for(int i=0;i<actualm;i++)sumc+=c[i];
if(suma>sumc)out();
for(int i=0;i<n;i++)if(a[i]>c[0])out();
for(int i=1;i<(1<<n);i++)dp[i]=INF;
dp[0]=0;
for(uint mask=0;mask<(1u<<n);mask++){
uint val=dp[mask];
if(val==INF)continue;
uint b=val>>27;
uint w=val&0x7ffffff;
uint cb=c[b];
uint unvis=((1u<<n)-1)^mask;
while(unvis>0){
int i=__builtin_ctz(unvis);
unvis&=unvis-1;
uint nw=w+a[i];
if(nw<=cb){
uint nval=(b<<27)|nw;
uint nxtmask=mask|(1u<<i);
if(nval<dp[nxtmask]){
dp[nxtmask]=nval;
}
}else{
uint nb=b+1;
uint nw2=a[i];
if(nb<(uint)actualm&&nw2<=(uint)c[nb]){
uint nval=(nb<<27)|nw2;
uint nxtmask=mask|(1u<<i);
if(nval<dp[nxtmask]){
dp[nxtmask]=nval;
}
}
}
}
}
if(dp[(1<<n)-1]==INF){
out();
}
printf("%d",(dp[(1<<n)-1]>>27)+1);
return 0;
}
|