首页 > 其他 > 详细

CF788C The Great Mixing BFS+思维

时间:2019-10-03 10:22:28      阅读:54      评论:0      收藏:0      [点我收藏+]

这个模型十分巧妙啊,好题好题~

code: 

#include <bits/stdc++.h>
#define N 3006 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int n,k,vis[N],in[N],dp[N];
vector<int>v;       
queue<int>q;  
int main() 
{ 
    int i,j; 
    // setIO("input"); 
    scanf("%d%d",&n,&k); 
    for(i=1;i<=k;++i) 
    {
        int x; 
        scanf("%d",&x), in[x]=1; 
    }
    memset(dp,0x3f,sizeof(dp));      
    for(i=0;i<=1000;++i) 
    {
        if(in[i]) 
        {
            v.push_back(n-i);   
            int x=n-i+1000;   
            dp[x]=1;     
            if(x==1000) 
            {
               printf("1\n"); 
               return 0; 
            }  
            q.push(x);      
        }
    }
    for(;!q.empty();) 
    {
        int u=q.front();q.pop();            
        for(i=0;i<v.size();++i) 
        {
            int x=u+v[i];          
            if(x>=0&&x<=2000&&dp[x]>dp[u]+1) 
            {
                dp[x]=dp[u]+1;     
                q.push(x);    
            }
        }
    } 
    if(dp[1000]>=100000) printf("-1\n"); 
    else printf("%d\n",dp[1000]); 
    return 0; 
}

  

 

CF788C The Great Mixing BFS+思维

原文:https://www.cnblogs.com/guangheli/p/11619099.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!