究极思路dp题（伪装spfa）
题面有一点错误，后来改了
应该是能够凑齐x输出1，否则输出-1
这题看数据范围就不是一道正经dp
但是a[i]的范围很是引人遐想
另外Q的范围是1e5也锁定了离线算法
考虑将a[1]作为去补齐其他组合的元素
对于dp[i]表示在模a[1]范围下能够到达i的最小价格
那么就可以用spfa进行转移
对于每个询问
查询dp[x%a[1]]是不是小于x就行了
贴代码
#include<bits/stdc++.h>
using namespace std;
long long dis[1000005],n,q,shu,a[1000005],pd[1000005];
queue <int> que;
void spfa()
{
memset(dis,127,sizeof(dis));
que.push(0);
dis[0]=0;
while(!que.empty())
{
int x=que.front();
que.pop();
pd[x]=0;
for(int i=2;i<=n;i++)
{
int y=(x+a[i])%a[1];
if(dis[y]>dis[x]+a[i])
{
dis[y]=dis[x]+a[i];
if(!pd[y])
{
que.push(y);
pd[y]=1;
}
}
}
}
}
int main()
{
freopen("hungry.in","r",stdin);
freopen("hungry.out","w",stdout);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
spfa();
for(int i=1;i<=q;i++)
{
scanf("%I64d",&shu);
if(dis[shu%a[1]]<=shu)
{
printf("1\n");
}
else printf("-1\n");
}
return 0;
}1、从 vim 一题看线头 DP 的扩展应用
2、自已参考做的读写配置文件(测试完整):AppConfig
3、unity_UGUI养成之路02
4、DelphiXE10.2怎么安装文本转语音(TTS)语音转文本(SR)控件（XE10.2+WIN764）
5、CSS 渐变效果在IE下无效？