【BZOJ2253】[BJWC2010]纸箱堆叠

这个题目显然是一个严格化的三维偏序,即
a_i < a_j,b_i < b_j,c_i < c_j
那么问题显然就变成cdq优化转移了,注意这里是严格的,因此我们划分区间的时候,要保证所有第一维相同的数字在同一个区间,而不会被mid给分开……但是这样真的不会破坏复杂度吗我也不知道……

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e5 + 10;

lo a, p, n, lsh[ms], ta, tre[ms], ans;//lsh == 离散化 

struct node
{
    lo x, y, z, ans;

    inline bool operator < (const node &a) const
    {
        if(y != a.y)
            return y < a.y;
        return z < a.z;
    }
}ter[ms], tmp[ms];

inline bool cmp(node a, node b)
{
    if(a.x != b.x)
        return a.x < b.x;
    if(a.y != b.y)
        return a.y < b.y;
    return a.z < b.z;
}

inline int lowbit(int x)
{
    return x & (-x);
}

inline void change(int x, lo v)
{
    while(x <= ta)
        tre[x] = max(tre[x], v), x += lowbit(x);    
}

inline lo ask(int x)
{
    lo rt = 0;
    while(x)
        rt = max(rt, tre[x]), x -= lowbit(x);
    return rt;
}

inline void clear(int x)
{
    while(x <= ta)
    {
        if(tre[x])
            tre[x] = 0;
        else
            break;
        x += lowbit(x);
    }
}

void merge(int l, int r)
{
    if(l >= r)
        return;
    int mid = (l + r) >> 1, t1 = mid, t2 = mid + 1; mid = ms;
    while(t1 >= l || t2 <= r)//为了保证三维偏序的严格,我们把第一维所有相同的数字划在一起而不是分到左右两边 
    {
        if(t1 >= l && ter[t1].x != ter[t1 + 1].x)
        {
            mid = t1; break;
        }
        if(t2 <= r && ter[t2].x != ter[t2 - 1].x)
        {
            mid = t2 - 1; break;
        }
        t1 --, t2 ++;
    }
    if(mid == ms)//如果第一维直接都是一样的,那不用算了 
        return;
    merge(l, mid);//先去计算左边 
    t1 = l, t2 = mid + 1;
    sort(ter + l, ter + mid + 1), sort(ter + mid + 1, ter + r + 1);
    for(ri i = l; i <= r; i ++)
    {
        if(t2 > r || (t1 <= mid && ter[t1].y < ter[t2].y))//如果右边的区间算完了,或者左边要比右边小 
            change(ter[t1].z, ter[t1].ans), t1 ++;
        else//否则更新答案 
            ter[t2].ans = max(ter[t2].ans, ask(ter[t2].z - 1) + 1), t2 ++;
    }
    for(ri i = l; i <= mid; i ++)//清空左边的影响 
        clear(ter[i].z);
    sort(ter + mid + 1, ter + r + 1, cmp), merge(mid + 1, r);//再去算右边 
}

int main()
{
    re(a), re(p), re(n);
    lo tmp = a % p;
    for(ri i = 1; i <= n; i ++, tmp = tmp * a % p)
    {
        ter[i].x = tmp, tmp = tmp * a % p, ter[i].y = tmp, tmp = tmp * a % p, ter[i].z = tmp;
        if(ter[i].x > ter[i].y)//提前排好序 
            swap(ter[i].x, ter[i].y);
        if(ter[i].x > ter[i].z)
            swap(ter[i].x, ter[i].z);
        if(ter[i].y > ter[i].z)
            swap(ter[i].y, ter[i].z);
        ter[i].ans = 1;
        lsh[++ ta] = ter[i].x, lsh[++ ta] = ter[i].y, lsh[++ ta] = ter[i].z;
    }
    sort(lsh + 1, lsh + 1 + ta);
    ta = unique(lsh + 1, lsh + 1 + ta) - lsh - 1;
    for(ri i = 1; i <= n; i ++)//离散化 
    {
        ter[i].x = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].x) - lsh;
        ter[i].y = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].y) - lsh;
        ter[i].z = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].z) - lsh;
    }
    sort(ter + 1, ter + 1 + n, cmp);
    merge(1, n);//cdq 
    for(ri i = 1; i <= n; i ++)//比较答案 
        ans = max(ans, ter[i].ans);
    printf("%lld", ans);
}

【算法】斜率优化

这个东西其实挺有意思的,之前学了好几次,这次专门来写写
斜率优化顾名思义,跟斜率有关系。我理解的斜率优化就是,将你的dp式子转化成一个函数形式。这个函数应该多半是一次函数。然后你的目的就是去根据题目去按照斜率寻找转移状态。
接下来放例题
luoguP2365任务安排
这个题目我们首先要用一个小技巧。我们现在这个dp很蛋疼,因为我不知道转移到i这个点的时候我划分成了几块。所以我们可能会考虑\(dp[i][j]\)这么一个状态来表示目前考虑到第i个人j块的最小代价。这样我们转移就成\(n^{3}\)了。
但是事实上这并不需要。我们不考虑之前有多少块了,而是这么想,\(dp[i]\)表示目前考虑完前i个,并且i是最后一块结尾的最小代价。转移的时候我们这么转移,考虑新生成的一块对后面所有点产生的影响,比如我们从\(j\)这个点开始划分块,一直划分到\(i\),那么你考虑我们目前对于j后面那些点都增加了s时间。
所以这个地方我就只需要一个dp状态\(dp[i]\)就可以了。这样显然是没有后效性的。我们复杂度也随之降到了\(n^{2}\)。对于luogu这个题目来说这是一个足够的复杂度了。但是在bzoj还有一个加强了两轮的版本,其中加强的一部分是要求复杂度在\(nlogn\)及其以下的复杂度。所以我们首先需要从这里优化复杂度。
首先我们对时间和花费求个前缀和,这样便于我们接下来计算
我们考虑现在这个dp方程
\(dp[i] = min(dp[j] + s(c[n] – c[j]) + t[i](c[i] – c[j]))\)
s和题意一致,c[i]表示花费的前缀和,t[i]表示所消耗是时间的前缀和,那么对于每一个j来说,我们都可以移项变形,那么方程变成了
\(dp[j] = dp[i] – s(c[n] – c[j]) – t[i](c[i] – c[j]) = (t[i] + s)c[j] + dp[i] – t[i] * c[i] – s * c[n]\)
我们观察这个最后的式子,是不是有点类似于\(y = kx + b\)
也就是说,在这个式子里面,\(dp[j]\)是\(y\),\((t[i] + s)\)是斜率
\(dp[i] – t[i] * c[i] – s * c[n]\)这是一个常数
那么我要让\(dp[i]\)尽可能小,也就说这个常数要尽可能的小。
那么你手画下就会发现这么一个事情,对于我新生成的这条直线,也就是\(dp[j]\)的表达式,我把这条直线向上不停的移动,我最早碰到的那个点,他就是\(b\)最小的一个


也就是这两个图画的这样。我们继续手玩会进一步得出结论,我们按照\(x\)排序,这个时候你会发现,设我们这个直线的斜率为\(k_{0}\)那么也就是\(k_{1} < k_{0} < k_{2}\)。稍微思考下你就会发现这是个单调递增的函数
大概就是长这样



这样我们就可以发现,我只需要维护一个下凸壳就可以了。因为这个地方\(x\)具有单调性,所以我们可以直接队列维护,考虑到\(c[i]\)也是如此,我们可以发现在这个题目里面甚至可以直接一个单调队列就行了,每次转移队首的。因为你看刚才那个不等式,那些\(k_{1}\)现在如果用不到,以后也不会,所以可以直接不考虑。
然后这个题目就做完了。放一下dalao的博客,图也是从dalao那里借来的,已经说过了qwq斜率优化学习笔记

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, s, dp[5050], ta, he, t[5050], c[5050], q[5050];

int main()
{
    re(n), re(s);
    for(ri i = 1; i <= n; i ++)
        re(t[i]), re(c[i]), t[i] += t[i - 1], c[i] += c[i - 1];
    q[he = ta = 1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        while(he < ta && dp[q[he + 1]] - dp[q[he]] <= (t[i] + s) * (c[q[he + 1]] - c[q[he]]))
            he ++;
        dp[i] = dp[q[he]] + s * (c[n] - c[q[he]]) + t[i] * (c[i] - c[q[he]]);
        while(he < ta && (dp[i] - dp[q[ta]]) * (c[q[ta]] - c[q[ta - 1]]) <= (dp[q[ta]] - dp[q[ta - 1]]) * (c[i] - c[q[ta]]))
            ta --;
        q[++ ta] = i;
    }
    printf("%d", dp[n]);
    system("pause");
}

但是刚才说过了,这个题目还有进击版,bzoj2726任务安排
这个题目首先……你数组按30w吧,时间可正可负,并且所有的变量longlong都存的下。
那么现在\(t[i]\)不单调了,但是\(c[i]\)还是单调的
还记得刚才我说的\(nlog_{n}\)吗,现在确实截的直线的斜率并不单调,但我们依然可以用单调队列维护下凸包,然后二分去查找最早满足那个不等式的地方就行了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo ms = 300030;

lo n, s, t[ms], c[ms], dp[ms], q[ms], he, ta;

inline lo find(lo x)
{
    lo l = he, r = ta;
    if(l == r)
        return q[he];
    while(l < r)
    {
        lo mid = (l + r) >> 1;
        if(dp[q[mid + 1]] - dp[q[mid]] > x * (c[q[mid + 1]] - c[q[mid]]))
            r = mid;
        else
            l = mid + 1;
    }
    return q[l];
}

int main()
{
    re(n), re(s);
    for(ri i = 1; i <= n; i ++)
        re(t[i]), re(c[i]), t[i] += t[i - 1], c[i] += c[i - 1];
    he = ta = 1;
    for(ri i = 1; i <= n; i ++)
    {
        lo pos = find(s + t[i]);
        dp[i] = dp[pos] + s * (c[n] - c[pos]) + t[i] * (c[i] - c[pos]);
        while(he < ta && (dp[i] - dp[q[ta]]) * (c[q[ta]] - c[q[ta - 1]]) <= (dp[q[ta]] - dp[q[ta - 1]]) * (c[i] - c[q[ta]]))
            ta --;
        q[++ ta] = i;
    }
    printf("%lld", dp[n]); system("pause");
}

还是dalao的博客2018.09.05 bzoj2726: [SDOI2012]任务安排(斜率优化dp+二分)

【luoguP3746】组合数问题

这个题目……开始我yy了一个dp方程为\(dp[i] = dp[i – 1] + C_{nk}^{ik + r}\),然后矩阵一波发现emmmmmm里面有个组合数是会随着i的增长,m不断改变的。然后我就弃疗了。看完题解以后顿时觉得自己是个zz啊
组合数的递推公式\(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\),那么我这个式子加个\(\\sum\)也不是不行啊
于是式子变成了这样\(\sum C_{n}^{m} = \sum C_{n – 1}^{m – 1} + \sum C_{n – 1}^{m}\)
然后我就可以设置dp[i][j] = dp[i-1][j-1] + dp[i-1][j],dp[i][j]表示n为i的时候且m为a*k+j的时候的答案
这个东西显然可以矩阵快速幂优化
但是其实这个方程这么写是错的
j0的时候j-1不就是-1了吗
那么真正的方程式为dp[i][j] = dp[i – 1][j] + dp[i – 1][(j – 1 + k) % k]

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, p, k, r;

struct in
{
    lo a[55][55];
}a, ans;

in operator * (in x, in y)
{
    in c; memset(c.a, 0, sizeof(c.a));
    for(ri kk = 0; kk < k; kk ++)
        for(ri i = 0; i < k; i ++)
            for(ri j = 0; j < k; j ++)
                c.a[i][j] = (c.a[i][j] + x.a[i][kk] * y.a[kk][j] % p) % p;
    return c;
}

int main()
{
    re(n), re(p), re(k), re(r), n *= k;
    for(ri i = 0; i < k; i ++)
        a.a[i][i] ++, a.a[(i - 1 + k) % k][i] ++;
    for(ri i = 0; i < k; i ++)
        ans.a[i][i] = 1;
    while(n)
    {
        if(n & 1)
            ans = a * ans;
        a = a * a, n >>= 1;
    }
    printf("%lld", ans.a[0][r]);
}

【洛谷P4882】lty loves 96!

开始的时候看到这个题目有点懵逼,因为没仔细看条件,以为有几个条件是保证对于每一个abc
我们考虑,对于一个数字,只有最后两个加进去的才是有意义的,之前怎么摆最后只需要保留已经满不满足第三个大条件即可。所以我们可以设一个裸的状态dp[i][j][x][y][0/1]表示当前已经放了i位数,有j个9/6,第i位为y,i-1位为x,是否满足第三个条件的方案数。那么转移方程也比较显然了,这里就不再写转移方程,具体分析下情况。我们每次转移的时候枚举最后三位数。如果后三位数能满足条件,则能从非法转移到合法,否则只能从非法转移到非法。原本合法的一定转移过来。
注意,这个题目是认为倒数第三位为模数c的qwq

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int mo = 1e8;

int n, m, t;

struct in
{
    int a[55];
    void init(int x)
    {
        memset(a, 0, sizeof(a)), a[a[0] = 1] = x;
    }
}dp[2][51][10][10][2];

in operator + (in a, in b)
{
    int d = max(a.a[0], b.a[0]);
    for(ri i = 1; i <= d; i ++)
        a.a[i] += b.a[i], a.a[i + 1] += a.a[i] / mo, a.a[i] %= mo;
    while(a.a[d + 1] > 0)
        d ++, a.a[d + 1] += a.a[d] / mo, a.a[d] %= mo;
    a.a[0] = d; return a;
}

inline void print(in a)
{
    int mx = a.a[0]; printf("%d", a.a[mx]);
    for(ri i = mx - 1; i >= 1; i --)
        printf("%08d", a.a[i]);
    printf("\n");
}

inline bool check(int x)
{
    return x == 9 || x == 6;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    //freopen("qwq.out", "w", stdout);
    re(n), re(m);
    if(n == 1)
    {
        printf(m == 0 ? "9" : "2"); return 0;
    }
    else if(n == 2)
    {
        printf(m == 0 ? "90" : (m == 1 ? "34" : "4")); return 0;
    }
    for(ri i = 0; i < 10; i ++)
        for(ri j = 0; j < 10; j ++)
            dp[t][check(i) + check(j)][i][j][0].init(1);
    for(ri i = 3; i <= n; i ++)
    {
        t ^= 1;
        for(ri j = 0; j < i; j ++)
            for(ri x = 0; x < 10; x ++)
                for(ri y = 0; y < 10; y ++)
                    dp[t][j][x][y][0].init(0), dp[t][j][x][y][1].init(0); 
        for(ri j = 0; j < i; j ++)
            for(ri x = 0; x < 10; x ++)
                for(ri y = 0; y < 10; y ++)
                    for(ri z = 0; z < 10; z ++)
                    {
                        dp[t][check(z) + j][z][y][1] = dp[t][check(z) + j][z][y][1] + dp[t ^ 1][j][y][x][1];
                        if(check(x + y + z)
                        || (x && check((y * y + z * z) % x)))
                            dp[t][check(z) + j][z][y][1] = dp[t][check(z) + j][z][y][1] + dp[t ^ 1][j][y][x][0];
                        else
                            dp[t][check(z) + j][z][y][0] = dp[t][check(z) + j][z][y][0] + dp[t ^ 1][j][y][x][0];
                    }
    }
    in ans; ans.init(0);
    for(ri i = 1; i < 10; i ++)
        for(ri j = 0; j < 10; j ++)
            for(ri k = m; k <= n; k ++)
                ans = ans + dp[t][k][i][j][1];
    print(ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

【洛谷P3266】[JLOI2015]骗我呢

更正题面,对于\(1 \le i \le n\); \(1 \le j <m\) 满足 \(x_{i,j} < x_{i,j+1}\)
对于每一行,一共有m个数,值域为\([0, m]\),而且每行的数单调上升,很显然,\([0, m]\),这些只有一个数不出现。并且我们每次新加一行的时候,只需要考虑上一行的状态就行了,因此我们列出一个朴素的dp状态,设dp[i][j]表示当前已经放了i行,最后一行缺的是j,转移方程为\(dp_{i,j} = \sum_{k = min(0, j + 1)}^{j + 1}dp_{i – 1, k}\),这个东西我们可以算一下就知道了,当m = 4,的时候,目前为0134,上一行为0124,这样是合法的,但是上一行为0123的时候这样就不合法了
那么现在我们将方程式变一下形,\(dp_{i, j} = dp_{i, j – 1} + dp_{i – 1, j + 1}\),可以发现现在我们每次转移只会向右一格&向左下一格。在这里题目的美妙即将展开了。我们现在可以把式子转化成图。
就是这么一张图片,问你从平行四边形右下走到左上且不跨越A B两直线的方案数。这样我们有一个比较显然的思路,用总方案数减去不合法的方案数。那么我们用A表示这个方案跨越了左边的边界,用B表示这个方案跨越了右边的边界。我们设最左下角的为\((0, 0)\),左侧直线表达式为\(y_{A} = x + 1\),右侧表达式为\(y_{B} = x – (m + 2)\)
那么我们的目的是去除形如ABABBBBAAAABABABAAAB这些方案。对于刚才那个方案,我们发现连续的一段区间可以直接缩成一个字母——他一直在跨越同一个边界,没有意义。所以刚才那个可以缩水成ABABABABABAB这样的方案。接下来,我们令初始点为\((n+m+1,n)\),重复以下操作:
将当前点以直线A为对称轴翻转,然后将原点到当前点的方案数从答案中减去,再将当前点以直线B为对称轴翻转,把原点到当前点的方案给加上,一直重【复】复【读】,直到当前点的任意一维坐标小于0结束。
这样子我们就相当于将以A和AB为后缀的方案删除了,然后把BA和BAB为后缀的方案加回去……所以实际上我们到最后是把以A为前缀的方案删除了。
同理再对B做一遍这样的操作。总方案为//(C_{2 * n + m + 1}^{n})。
放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

const lo mo = 1e9 + 7;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, m, d, ans, inv[3000010], fac[3000010];

lo c(lo x, lo y)
{
    if(x < y)
        return 0;
    return fac[x] * inv[y] % mo * inv[x - y] % mo;
}

lo cc(lo x, lo y)
{
    if(x < 0 || y < 0)
        return 0;
    return c(x + y, y);
}

inline void change(lo &x, lo &y, lo num)
{
    swap(x, y), x += num, y -= num;
}

inline lo ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return rt;
}

int main()
{
    re(n), re(m), d = max(n, m), inv[1] = inv[0] = fac[1] = fac[0] = 1;
    for(ri i = 2; i <= 3000000; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[3000000] = ksm(fac[3000000], mo - 2);
    for(ri i = 2999999; i >= 2; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    lo lx = n + m + 1, ly = n;
    ans = cc(lx, ly);
    while(lx >= 0 && ly >= 0)
        change(lx, ly, -1), ans -= cc(lx, ly), change(lx, ly, m + 2), ans += cc(lx, ly), ans %= mo;
    lx = n + m + 1, ly = n;
    while(lx >= 0 && ly >= 0)
        change(lx, ly, m + 2), ans -= cc(lx, ly), change(lx, ly, -1), ans += cc(lx, ly), ans %= mo;
    ans = (ans % mo + mo) % mo, printf("%lld", ans);
    return 0;
}

【NOI OpenJudge 7627】鸡蛋的硬度

这个题时隔一年多以后我看这个题目还是一脸懵逼,看完题解后恍然大悟。我们设dp[i][j]表示当前有i个楼层,用了j个鸡蛋最坏需要丢多少次,那么转移我们可以通过分解成子问题来做。dp[i][j] = min(dp[i][j], max(dp[k – 1][j – 1], dp[i – k][j]) + 1)。这个max什么意思呢?

这个图蓝色的部分就是第k层红色的部分就是dp[i – k][j],即表示我们在k这一层没有把鸡蛋摔碎,楼上那些需要几次确定答案,绿色的部分表示我们在k这一层鸡蛋被摔碎了,下面k – 1层需要用j – 1个鸡蛋只能用确定了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, m, dp[110][15];

int main()
{
    while(~ scanf("%d%d", &n, &m))
    {
        for(ri i = 1; i <= n; i ++)
            for(ri j = 0; j <= m; j ++)
                dp[i][j] = i;
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= i; j ++)
                for(ri k = 2; k <= m; k ++)
                    dp[i][k] = min(dp[i][k], max(dp[j - 1][k - 1], dp[i - j][k]) + 1);
        printf("%d\n", dp[n][m]);
    }
}