AtCoder ABC 268 D

Question

AtCoder ABC 268 D

有1个wa，2个re

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,x,max=0;
    cin>>n>>x;
    int a[n],b[n];
    for(int i=0;i<n;++i)
    {
        cin>>a[i]>>b[i];
        max+=a[i]*b[i];
    }
    bool m[max+1]={1};
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<b[i];++j)
        {
            for(int k=max;k>=a[i];--k)
            {
                if(m[k-a[i]])
                {
                    m[k]=1;
                }
            }
        }
    }
    cout<<(m[x]?"Yes":"No");
    return 0;
}

hard03 wa hard 09 re rand 03 re

试过map，但tle，用bool打标记，但会re

能帮忙调一下吗？

Answer 1

这段代码是一种背包问题的实现，它使用了一维bool数组来存储每种物品是否被选中。但是由于数组的大小是确定的，所以如果最大物品数量过大就会导致空间不足，导致RE。

解决方案是使用动态数组，如std::vector。

如果你在使用map时TLE了，那是因为map是一种高度封装的数据结构，它在插入和查询数据时需要进行额外的操作，因此会比使用数组慢很多。

另外，在背包问题中，我们通常使用01背包问题的解法，这是一种基于动态规划的解法，这种解法是在O(nx)的时间复杂度内解决问题的，而完全背包问题的复杂度是O(nx*x)的。所以我建议你换一种方法。

代码如下：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,x,max=0;
    cin>>n>>x;
    vector<int> a(n),b(n);
    for(int i=0;i<n;++i)
    {
        cin>>a[i]>>b[i];
        max+=a[i]*b[i];
    }
    vector<bool> m(max+1,false);
    m[0]=true;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<b[i];++j)
        {
            for(int k=max;k>=a[i];--k)
            {
                if(m[k-a[i]])
                {
                    m[k]=true;
                }
            }
        }
    }
    cout<<(m[x]?"Yes":"No");
    return 0
}