AT_abc286d 题解

板子

首先我们看到值域并不大。

因此可以维护值域，跑完全背包。

具体而言维护某一个值（小于 \(10000\) ）是否能被凑出来，然后枚举物品种类以及物品数量即可。

一般而言，完全背包要用一个辅助数组，但是也可以不用并调整枚举顺序，注意值域从大到小枚举，防止一个值被多次更新。

#include<bits/stdc++.h>
using namespace std;
const int maxn =1145141;
int n,x;
int a[maxn],b[maxn];
int Can[maxn];
int main(){
	Can[0]=1;
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
 	for(int k=1;k<=n;k++)
        for(int i=10000;i>=0;i--)
            for(int j=b[k];j>=1;j--)
                if(Can[i]==1)
                	Can[i+a[k]*j]=1;
	cout<<(Can[x]==1?"Yes\n":"No\n");
}