A simple Blog for wyx I've been down the bottle hoping.
3717: [PA2014]Pakowanie
发表于: | 分类: Oi | 评论:0 | 阅读:162

神奇的状压$dp$

开始的时候没想是状压……看24感觉非常的虚【忘了看90s的时限了

后来$Infinity37$教了我一发

首先我们把包按照容量从大到小排个序,因为显然如果$x$个小包能装的下$x$的大包当然也能装的下,所以先用大包

然后我们把物品的状态压压压,枚举这个状态,计$f(sta)$为物品的状态为$sta$的时候的答案,$g(sta)$为当前状态下最后一个包的剩余容量枚举他是由哪一个状态而来转移即可

转移的条件有点多但是挺好想的

不知道为什么我跑的这么快

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int Maxn = 16800000;
#define lowbit(x) ((x)&(-x))
 
int F[Maxn], G[Maxn] , a[Maxn], c[100+5];
int n,m,tmp;
 
inline bool cmp(const int &a,const int &b) {
    return a > b;
}
 
int main () {
    cin >> n >> m;
    int all = (1<<n);
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=m;++i) cin >> c[i];
    sort(c+1,c+m+1,cmp);
    for(int i=n;i;--i) a[1<<(i-1)] = a[i];
    int tmp, x;
    register int i;
    for(i=1;i<all;++i) {
        F[i] = m + 1,G[i] = -1;
        for(int j=i;j;j-=tmp) {
            tmp = lowbit(j);
            x = i - tmp;
            if (a[tmp]<=G[x]&&(F[x]<F[i]||(F[x]==F[i]&&G[x]-a[tmp]>G[i]))) F[i]=F[x],G[i]=G[x]-a[tmp];
            else if((F[x]+1<F[i]||(F[x]+1==F[i]&&c[F[x]+1]>G[i]+a[tmp]))&&c[F[x]+1]>=a[tmp]) F[i]=F[x]+1,G[i]=c[F[i]]-a[tmp];
        }
    }
    if(F[all-1] > m) puts("NIE");
    else cout << F[all-1] << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP