D - Money in Hand

https://atcoder.jp/contests/abc286/tasks/abc286_d

思路

创建可访问性标记map

vis

默认设置

vis[0] = true

表示 0 的钱数，可以凑成，不用选取任何硬币

对于 A1 B1 做可访问性标记

vis[A1] = true

vis[2A1] = true

vis[3A1] = true

...

vis[B1*A1] = true

对于 A2 B2 做可访问性标记

对于所有已经标记为true的点： A2, 2A3, ... ,  B2*A2

任取一个 point

叠加上 A2 的增量的所有情况，构成所有的新的可访问点：

point + A2 ,  point + 2A2, ..., point + B2*A2

vis[point + A2] = true

vis[point + 2A2] = true

...

vis[point + B2*A2] = true

.....

最后，判断 vis[x] 是否 true

Code

https://atcoder.jp/contests/abc286/submissions/38242800

int n, x;
int a[60];
int b[60];
map<int, bool> vis;
 
int main()
{
    cin >> n >> x;
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
 
    vis[0] = true;
    for(int i=1; i<=n; i++){
        int ai = a[i];
        int bi = b[i];
 
        vector<int> curpoints;
        for(auto it: vis){
            int point = it.first;
 
            curpoints.push_back(point);
        }
 
        for(auto it: curpoints){
            int point = it;
            
            for(int j=0; j<=bi; j++){
                int newpoint = point+j*ai;
                if (newpoint > x){
                    break;
                }
                
                vis[newpoint] = true;
            }
        }
    }
 
    if (vis[x] == true){
        cout << "Yes" << endl;
        return 0;
    }
 
    cout << "No" << endl;
 
    return 0;
}