BZOJ2612 [Poi2003]Sums

2019-04-14 21:09发布

站内文章 / 模拟电子
15380 0 1375
任取一个物品，假设其体积为V，那么我们可以在模V的意义下做背包，f[i]表示对于模V得i的物品，当体积>=f[i]时能被表示出来 那么就可以跑最短路了 不妨取体积最小那个，dijkstra的话理论复杂度是(5000*50000)logn，但是跑的飞起 事实上我们可以取最大那个，然后令f[i]表示表示对于模V得i的物品，当体积>=f[i]*V时能被表示出来 这样的话边权都为0或者1，那么我们可以01bfs，理论复杂度(5000*50000)，但是跑不过 dijkstra: #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAXN 50010 #define MAXM 1010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 struct data{ int x; int v; data(){ } data(int _x,int _v){ x=_x; v=_v; } friend bool operator <(data x,data y){ return x.v>y.v; } }; int n; int a[MAXN]; int mn; int f[MAXN]; priority_queueq; bool vis[MAXN]; void dijkstra(){ int i,x; memset(f,0x3f,sizeof(f)); f[0]=0; q.push(data(0,0)); while(!q.empty()){ x=q.top().x; q.pop(); if(vis[x]){ continue ; } vis[x]=1; for(i=1;i<=n;i++){ if(f[x]+a[i]=f[x%mn]?"TAK ":"NIE "); } return 0; } /* 3 2 5 7 6 0 1 4 12 3 2 */ 01bfs: #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAXN 50010 #define MAXM 1010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 int n; int a[MAXN]; int mx; int f[MAXN]; int q[MAXN],hd,tl; int Q[MAXN],HD,TL; void bfs(){ int i,x; memset(f,0x3f,sizeof(f)); f[0]=0; q[tl++]=0; while(hd!=tl){ Q[TL++]=q[hd++]; int thd=HD; while(HD!=TL){ x=Q[HD++]; for(i=1;i<=n;i++){ if(f[(x+a[i])%mx]>INF){ if(x+a[i]INF){ if(x+a[i]>=mx){ f[x+a[i]-mx]=f[x]+1; q[tl++]=x+a[i]-mx; } } } } } } int main(){ int i,j,x; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); } mx=a[n]; bfs(); scanf("%d",&n); while(n--){ scanf("%d",&x); printf(x/mx>=f[x%mx]?"TAK ":"NIE "); } return 0; } /* 3 2 5 7 6 0 1 4 12 3 2 */

热门文章