题解 | #小红不想做完全背包 （hard）#

D.小红不想做完全背包 （hard）

多源同余最短路做法:

考虑到以所有a[i]%p为起点，初始化使dis[a[i]%p]=1

那么终点即为dis[0]

具体代码如下：

#include<bits/stdc++.h>
#define endl '\n' 
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f,P=131;
vector<PII>e[N];
int dis[N],vis[N];
void dijkstra(int n)
{
	priority_queue<PII,vector<PII>,greater<PII>> q;
	for(int i=0;i<n;i++)
    {
        if(dis[i])q.push({dis[i],i});
        else dis[i]=inf;
    }  
	while(q.size())
	{
		int t=q.top().y;
		q.pop();
		if(vis[t])continue;
		vis[t]=1;
		for(auto i:e[t])
		{
			if(dis[t]+i.y<dis[i.x])
			{
			   dis[i.x]=dis[t]+i.y;
		       q.push({dis[i.x],i.x});
			}
		}
	}
}
void solve(int T)
{
    int n,p;
    cin>>n>>p;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(int j=0;j<p;j++)
        {
            e[j].push_back({(j+a[i])%p,1});
        }
        dis[a[i]%p]=1;
    }
    dijkstra(p);
    cout<<dis[0]<<endl;
}
signed main()
{
    bool multitest=0;
    //cout<<setiosflags(ios::fixed),cout.precision(2);
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int _t=1;
    if(multitest)cin>>_t;
    for(int i=1;i<=_t;i++)
    {
        solve(i);
    }
    return 0;
}