$O(nm)$ 对付 $10^5$ 数据，显然会T飞
建议参考题解
by liangbowen @ 2022-08-22 14:01:47
现在发现a[i]<=10 b[i]<=10，原来是完全背包（二进制优化）
by YuRuochen @ 2022-08-22 14:04:11
多重背包
by YuRuochen @ 2022-08-22 14:04:25
@[YuRuochen](/user/658786) 是 01 背包啊，只是说不能用朴素做法做而已
by liangbowen @ 2022-08-22 14:08:46
@[liangbowen](/user/367488)
现在变成30分，WA了。
```
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,p,q[15][15],a[1000010],b[100010],dp[100010];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
q[x][y]++;
}
for(int i=0;i<=10;i++){
for(int j=0;j<=10;j++){
if(q[i][j]){
int c=q[i][j],d=1;
while(c){
if(c%2==1){
p++;
a[p]=d*i;
b[p]=d*j;
}
c>>=1;
d<<=1;
}
}
}
}
for(int i=1;i<=p;i++){
for(int j=m;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
if(dp[m]>=k) printf("yes\n");
else printf("no\n");
printf("%d",dp[m]);
return 0;
}
by YuRuochen @ 2022-08-22 14:13:28
@[liangbowen](/user/367488) ?
by YuRuochen @ 2022-08-22 14:16:34
@[liangbowen](/user/367488) https://www.luogu.com.cn/blog/DarkMoon1/solution-p2306
by Micnation_AFO @ 2022-08-22 14:32:25
@[Leap_hash_jperm](/user/574944) 指的是本质01背包。不过我的确表述不清了()
by liangbowen @ 2022-08-22 14:35:04
我是用多重背包，AC代码如下：
```
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,p,q[15][15],a[1000010],b[100010],dp[100010];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
q[x][y]++;
}
for(int i=0;i<=10;i++){
for(int j=0;j<=10;j++){
if(q[i][j]){
int c=q[i][j],d=1;
while(c>d){
p++;
a[p]=d*i;
b[p]=d*j;
c-=d;
d<<=1;
}
p++;
a[p]=c*i;
b[p]=c*j;
}
}
}
for(int i=1;i<=p;i++){
for(int j=m;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
if(dp[m]>=k) printf("yes\n");
else printf("no\n");
printf("%d",dp[m]);
return 0;
}
by YuRuochen @ 2022-08-22 15:18:55