状吔DP get ！

A4paper · 2018-09-03 15:43:44 · 个人记录

normal：

传送门

求方案数

个人感觉，

难点在预处理上呢。。。

不得不吐槽一下这个老鼠蛋蛋。。。。（美国人就是社会）

struct node{
    int x,y;
}point[30];

inline void dp()
{
    for(int i=0;i<(1<<cnt)-1;i++)
    for(int j=1;j<=cnt;j++)
    {
        if(i & 1<<(j-1)) continue;
        for(int k=1;k<=cnt;k++)
        {
            if((1<<(k-1)) & i)
                f[i|(1<<(j-1))][j] = min(f[i|(1<<(j-1))][j],f[i][k]+map[j][k]);
        }
    }
}

int main(void)
{
    while(scanf("%d%d",&n,&m) != EOF)
    {
        cnt = 1;
        memset(f,0x3f,sizeof f);
        memset(map,0,sizeof map);
        f[1][1] = 0;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char c;
            cin >> c;
            if(c == 'L')    point[1] = (node){i,j};
            if(c == '#')    point[++cnt] = (node){i,j};
        }
        for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=cnt;j++)
            map[i][j] = map[j][i] = max(abs(point[i].x-point[j].x),abs(point[i].y-point[j].y));
        dp();
        ans = 0x3f3f3f3f;
        for(int i=1;i<=cnt;i++)
            ans = min(ans,f[(1<<cnt)-1][i]+map[i][1]);
        cout << ans << endl;
    }
    return 0;
}

搜索：

传送门

当转移不好想或顺序不好确定的时候可以利用状压搜索来代替。

int n,m,ans=0x3f3f3f3f;
int f[1<<MAXN],dis[MAXN];
int map[MAXN][MAXN];

void dfs(int x)
{
    for(int i=1;i<=n;i++)
    {
        if((x&1<<(i-1)) == 0) continue;
        for(int j=1;j<=n;j++)
        {
            if(x&1<<(j-1) || map[i][j]==0x3f3f3f3f) continue;
            if(f[x|1<<(j-1)] > f[x]+dis[i]*map[i][j])
            {
                int temp = dis[j];
                f[x|1<<(j-1)] = f[x]+dis[i]*map[i][j];
                dis[j] = dis[i]+1;
                dfs(x|1<<(j-1));
                dis[j] = temp;
            }
        }
    }
}

signed main(void)
{
    memset(map,0x3f,sizeof map);
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        map[u][v] = map[v][u] = min(map[u][v],w);
    }
    for(int i=1;i<=n;i++)
    {
        memset(f  ,0x3f,sizeof f  );
        memset(dis,0x3f,sizeof dis);
        dis[i] = 1;
        f[1<<(i-1)] = 0;
        dfs(1<<(i-1));
        ans = min(ans,f[(1<<n)-1]);
    }
    cout << ans;
    return 0;
}

逆向：

传送门

多数状压都是用 或 来累加状态，而这道题则是用 异或 来扣去一个状态进行转移。

设 f[i] 表示在 i 状态下最多能买到第几个物品

怎么转移呢？

可以发现，如果用 1<<(i-1) 来表示第 i 个硬币的话，每种状态都可以扣去某一位的 1 表示没用这枚硬币前能买到第几个物品。

那么，记一个前缀和 len 表示物品总价，设 len 表示上一个状态能买到第几个物品，在使用第 j 个硬币时，当前状态就是 sum[len] + con[j] 所能买到的物品数。

int n,m,tot,ans=-1,Mx,cnt;
int con[20],state[20];
int sum[MAXN];
int f[1<<20];

int main(void)
{
    cin >> n >> m;
    Mx = (1<<n)-1;
    for(int i=1;i<=n;i++)
    {
        cin >> con[i];
        tot += con[i];
        state[i] = 1<<(i-1);
    }
    for(int i=1;i<=m;i++)
    {
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    for(int i=1;i<=Mx;i++)
    for(int j=1;j<=n;j++)
    {
        if(!(state[j]&i)) continue;
        int len = f[i^state[j]];
        len = upper_bound(sum+1,sum+1+m,sum[len]+con[j])-sum-1;
        f[i] = max(f[i],len);
    }
    for(int i=1;i<=Mx;i++)
    {
        if(f[i] != m) continue;
        cnt = 0;
        for(int j=1;j<=n;j++)
            if(i & state[j])
                cnt += con[j];
        ans = max(ans,tot-cnt);
    }
    cout << ans;
    return 0;
}

巩固：

传送门

与上一题类似。不过上一题用的填表法，这道题我用了刷表法

定义 f[i] 表示在 i 集合中最远能到达的位置。

枚举要填入那种电影，二分的找这种电影小于 f[i] 且最晚的开始时间，因为时长固定，所以越晚开始必定约优。

#define re register

int n,len,ans=100;
int a[22][MAXN],lenth[MAXN];
int f[1<<22];

inline void solve()
{
    for(re int i=0;i<=(1<<n)-1;i++)
    {
        if(f[i] == -1) continue;
        for(re int j=1;j<=n;j++)
        {
            if(i & (1<<(j-1))) continue;
            int now = upper_bound(a[j]+1,a[j]+1+a[j][0],f[i])-a[j]-1;
            if(now <= 0) f[i|(1<<(j-1))] = f[i];
            else f[i|(1<<(j-1))] = max(f[i|(1<<(j-1))],a[j][now]+lenth[j]);
        }
        if(f[i] >= len) ans = min(ans,__builtin_popcount(i));
    }
}

signed main(void)
{
    memset(f,-1,sizeof f);
    f[0] = 0;
    scanf("%d%d",&n,&len);
    for(re int i=1;i<=n;i++)
    {
        scanf("%d%d",&lenth[i],&a[i][0]);
        for(re int j=1;j<=a[i][0];j++)
            scanf("%d",&a[i][j]);
    }
    solve();
    if(ans == 100) puts("-1");
    else cout << ans;
    return 0;
}