星夜的蓝天

FZOJ T1作业[状态压缩动态规划]
FZOJ T1作业[状态压缩动态规划] pid47305056,话说P站被DNS污染加SNI阻断了呢…… 起...
扫描右侧二维码阅读全文
31
2018/07

FZOJ T1作业[状态压缩动态规划]

FZOJ T1作业[状态压缩动态规划]

pid47305056,话说P站被DNS污染加SNI阻断了呢……
47305056_p0.jpg

起先

   一开始看到数据范围n=20我还以为是考搜索卡了2个多小时……
   言归正传,本题的数据范围一看就应该猜到是考的状压dp,我们考虑用一个int类型来装当前状态,二进制上第i为1代表该位表示的作业已经完成,数学上以集合$\{S\}$表示

对于状态转移方程,不难想到

$F[\{S\}]=\min(F[\{S\}],F[\{S\}+j]+\max(0,time[\{S\}]-d[j]))$

接下来考虑找出方案,引用一下某大牛的solution

直接的想法是:对于状态p,枚举i的时候,相当于把i放在最后一位。
考虑从大到小枚举i。但这样还是错的,我们只能保证字典序逆序最大,但不能保证顺序最小
得到启发,从最后一位开始从小到大枚举i,可以保证逆序最小,但实际上就是我们要的答案。

但很遗憾的是……我没有看懂这段话,一开始考试的时候原题并没有要求如果存在多种方案以字典序输出,所以没太在意,不过既然提醒我们要考虑这点,那不妨想想解决办法吧。
考虑使用pre数组,因为我们在状态转移的时候,实际上对于每一个阶段的状态,我们都会碰到它的最优前置状态,每当当前状态被更新,那么我们就用一个pre数组储存当前状态的前置状态,即

if 状态被j更新:
  $pre[\{s\}]=j$

对于$time[\{s\}]$,即代表这种状态所需的作业时间,可以通过枚举所有状态,然后对枚举的状态单独计算,从而预处理得到。 那么我们就确定了起始状态$000000000$和最终状态$111111111111$(一共有n位,在此仅供直观理解) ,那么代码如下

ps:最近忙着建站,因为时间有点赶暂时还没写完题解,不过想必大家已经知道状态转移方程之后问题就不大了,自己摸索一下,poi!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;

int n, c[22], d[22];
int tim[1100040], f[1100050], pre[1300050];
int ans[22];
char name[22][55];

inline bool up(int &x, int y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%s%d%d", name[i], &d[i], &c[i]);
        }
        memset(tim, 0, sizeof(tim));
        for (int p = 0; p < (1 << n); ++p)
            for (int i = 0; i < n; ++i)
                if (!((1 << i) & p))
                    tim[p] += c[i];
        memset(f, 127, sizeof(f));
        f[0] = 0;
        for (int p = 1; p < (1 << n); ++p)
            for (int i = 0; i < n; ++i)
                if ((1 << i) & p)
                    if (up(f[p], f[p - (1 << i)] + max(0, tim[p - (1 << i)] - d[i])))
                        pre[p] = i;
        printf("%d\n", f[(1 << n) - 1]);
        int p = (1 << n) - 1;
        for (int i = 1; i <= n; ++i) {
            ans[i] = pre[p];
            p -= 1 << pre[p];
        }
        for (int i = 1; i <= n; ++i)
            printf("%s\n", name[ans[i]]);
    }
    //cerr << (double)clock() / CLOCKS_PER_SEC << endl;
}
最后修改:2018 年 10 月 31 日 11 : 33 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论

召唤看板娘