Training for Dynamic Programming

Posted by JHSN on July 4, 2017

2017 UESTC DP专题题解




题目链接:2017 UESTC Training for Dynamic Programming


Content

[CDOJ 1607] A - 大学生足球联赛
[CDOJ 1608] B - 暑假集训
[CDOJ 1610] C - 黑红梅方
[CDOJ 1606] D - 难喝的饮料
[CDOJ 1652] E - 都市大飙车
[CDOJ 1271] F - Search gold
[CDOJ 1006] G - 最长上升子序列
[CDOJ 1651] H - Uestc的命运之旅
[CDOJ 1653] I - 最小生成树?
[CDOJ 1654] J - 肆虐的病毒
[CDOJ 1689] K - 分序列
[CDOJ 1690] L - 这是一道比CCCC简单题难的简单题
[CDOJ 1691] M - 这是一道比CCCC简单题经典的中档题
[CDOJ 1692] N - 这是一道比CCCC简单题更有想象力的中档题



[CDOJ 1607] A - 大学生足球联赛

Problem

偶数 (2≤N≤66) 只球队参加球赛,采用循环制,共 N - 1 轮,每一轮有 N / 2 场比赛,每一轮中所有队伍均参加,每场比赛对阵组合均不同。也就是说每支球队打 N - 1 场比赛,每次比赛对阵的队伍不同。
例如 N = 4:
第 1 轮:1−2, 3−4
第 2 轮:1−3, 2−4
第 3 轮:1−4, 2−3

Solution

百度搜索“球赛安排”、“球队编排”有惊喜。

假设 N = 2k

第一轮对阵图:
1     vs     2
3     vs     4
    ......
2k-3  vs  2k-2
2k-1  vs    2k

使用轮转法,每次 1 固定,然后剩下的队伍顺时针(或逆时针)转一圈。  
1     vs     2
      ↙     ↑
3     vs     4
↓            ↑
    ......
↓            ↑
2k-3  vs  2k-2
↓            ↑
2k-1  -→    2k

以 N = 6 为例:
第一轮 第二轮  第三轮
1 - 2  1 - 4  1 - 6
3 - 4  2 - 6  4 - 5   ......
5 - 6  3 - 5  2 - 3

Code

const int N=100;
int i, j, k, m, n, n2;

int main()
{
    scanf("%d", &n);
    n2 = n >> 1;
    for (i = 1; i < n; i++)
    {
        m = n - i + 1;
        k = m;
        if (k > n) k = 1;
        printf("%d %d ", 1, m);
        for (j = 1; j < n2; j++)
        {
            k++;
            if (k > n) k = 2;
            m--;
            if (m < 2) m = n;
            printf("%d %d ", k, m);
        }
        puts("");
    }
    return 0;
}



[CDOJ 1608] B - 暑假集训

Problem

有 N (3≤N≤21) 名选手,三人一组,分成 N / 3 组,每个组的权值为 p(i,j,k),i,j,k 表示三个人,函数 p (1≤p≤100) 与 i,j,k 的顺序无关,求最大各组权值和。

Solution

2 ^ 21 = 2097152,所以肯定要用二进制压位记录状态。

如果写记忆化搜索,首先得计算一下情况数
用 f[n] 表示 N = n * 3 个选手的组合方案数
先选出 3 个人形成一组,剩下的 N - 3 个选手有 f[n-3] 种组合,因为每一种方案都会被计算 n 次,所以要除以 n
因此就有 f[n] = f[n-1] * C(N,3) / n
考虑实际搜索,f[n] 还要乘上 n 才差不多是时间复杂度

n N f[n] f[n]*n
1 3 1 3
2 6 10 20
3 9 280 840
4 12 15400 61600
5 15 1401400 7007000
6 18 190590400 1143542400
7 21 36212176000 253485232000

如果 xjb 搜索,最终的方案数是远远超过 f[n] 的,所以为了使得方案枚举不重复!
大力剪枝 1:对于某一种状态 x,如果从 1~N 第一个还没有被选的是 i,那么这个 i 一定要选,然后再在 i+1..N 里面枚举第二个人和第三个人

充分利用其无后效性,使用记忆化!
大力剪枝 2:用 f[x] 保存状态 x 的最大值,如果当前状态为 x,权值和为 w,那么 if (w ≤ f[x]) return;
这个时候其实已经过掉了,322 MS

322 MS 太慢了,来一发 A*! 大力剪枝 3:预处理出 pmax。如果当前状态为 x,权值和为 w,还有 tot 个人可以选,full 表示最终状态,如果满足 w + tot * pmax ≤ f[full],那么你往后无论再怎么搜也不可能比 f[full] 大。所以 if (w ≤ f[x] || w + tot * pmax ≤ f[full]) return;,这样能够大大优化靠近状态 full 的这一部分搜索
优化效果很显著,15 MS

后来考虑了一下如果用 DP 做,应该是用组数来划分阶段,然后对于每一个状态,枚举三个人进行决策,取所有决策中的最大值。
有转移方程:dp[x] = min{dp[y] + p(i,j,k)}
状态数 = Σ( C(N, i) ) | i=3,6,9,...,N 决策数 = Σ( C(N, i) * i^3 ) | i=3,6,9,...,N

N 状态数 决策数
3 1 27
6 21 756
9 169 21141
12 1365 367632
15 10921 5531625
18 87381 74314260
21 699049 924849765

这直接 dp 肯定要超时,肯定要化成从前往后推的形式,然后大力剪枝。。
感觉还不太好写,还不如直接用记忆化搜索的方式写?可能是我 DP 造诣还不够深。。

Code

const int N=25;
int full, cnt, n, ma, x, y, z, i, P;
int p[N][N][N];
int f[2100000];

void dfs(int x, int w, int i, int tot)
{
    if (w <= f[x] || w + tot * ma <= f[full]) return;
    f[x] = w;
    if (x == full) return;
    for (; i < n; i++)
    if (!(x & (1 << i))) break;
    for (int j = i + 1; j < n; j++)
    if (!(x & (1 << j)))
        for (int k = j + 1; k < n; k++)
        if (!(x & (1 << k)))
            dfs(x | (1 << i) | (1 << j) | (1 << k), w + p[i][j][k], i + 1, tot - 1);
}

int main()
{
    srand(123829344);
    scanf("%d", &n);
    full = (1 << n) - 1;
    for (i = n * (n - 1) * (n - 2) / 6; i; i--)
    {
        scanf("%d%d%d", &x, &y, &z);
        scanf("%d", &P);
        x--;y--;z--;
        p[x][y][z] = p[x][z][y] = P;
        p[y][x][z] = p[y][z][x] = P;
        p[z][x][y] = p[z][y][x] = P;
        ma = max(P, ma);
    }
    f[0] = -1;
    dfs(0, 0, 0, n / 3);
    printf("%d\n", f[full]);
    return 0;
}



[CDOJ 1610] C - 黑红梅方

Problem

一副扑克有黑桃、红桃、梅花、方块四种花色。
现在你把 N(4≤N≤1e18) 张扑克排成一行,每个位置都可以选择放置四种花色中的一种,只要这一行中出现了一组连续四张扑克牌花色各不相同的情况,就称该种排法为“卿式扑克序列”。
请你计算,对于 N 张扑克排成一行的 4^N 种排法中,共有多少种“卿式扑克序列”呢?

Solution

总方案数是 4 ^ N,考虑计算任意连续四张牌中存在至少两张花色相同的牌的方案数
二进制表示三张牌的状态 (0~63)
f(i,j) 表示前 i 张牌最后三张牌状态为 j 的方案数
那么 f(i,j) = sum{f(i-1,k)} 限制:k 表示 a b c 三张牌,j 表示 b c d 三张牌,j 和 k 即代表第 i-3 张到第 i 张这四张牌 —— a b c d,所以条件是 a b c d 不能各不相同。

对于这么大的数据范围,以及如此简单机械的递推方程,考虑 矩阵+快速幂 来优化算法
枚举 a b c d(即枚举状态 x=0~255),对于 a b c d 存在相同的情况,标记 A(k,j) = 1res(x & 63)++
那么整个转移可以转化为 res * A ^ (N-4) = res * (A ^ (N - 4))
对于后面一部分可以用快速幂,然后时间复杂度就优化到了 O(64^3 * logN)
最后再快速幂算一下 4^N,然后减一减就好了。。

Code

using namespace std;
typedef long long ll;
const int oo=1e9+9;
const int M=64;
ll n;

class Matrix {
public:
    ll **a;
    Matrix(bool init_option=true, int init_num=0)
    {
        a = new ll*[M];
        for (int i = 0; i < M; i++)
            a[i] = new ll[M];
        if (init_option) initial(init_num);
    }
    void initial(int init_num=0)
    {
        for (int row = 0; row < M; row++)
            for (int col = 0; col < M; col++)
                a[row][col] = init_num;
    }
    void diag_init(int init_num=1)
    {
        for (int row = 0; row < M; row++)
            a[row][row] = init_num;
    }
    void print()
    {
        for (int row = 0; row < M; row++)
        {
            for (int col = 0; col < M; col++)
                printf("%d ", a[row][col]);
            puts("");
        }
        puts("");
    }
    ll sum()
    {
        ll sumup = 0;
        for (int row = 0; row < M; row++)
            for (int col = 0; col < M; col++)
                sumup = (sumup + a[row][col]) % oo;
        return sumup;
    }
    void operator*=(const Matrix &r) {
        Matrix res;
        res.initial();
        for (int row = 0; row < M; row++) {
            for (int col = 0; col < M; col++) {
                for (int k = 0; k < M; k++) {
                    res.a[row][col] += a[row][k] * r.a[k][col];
                    res.a[row][col] %= oo;
                }
            }
        }
        *this = res;
    }
};

int main()
{
    scanf("%lld", &n);
    Matrix A;
    Matrix res;
    int ans;
    int tmp[4];
    for (int i = 0; i < 256; i++)
    {
        for (int j = 0; j < 4; j++)
            tmp[j] = (i & (3 << (j<<1))) >> (j<<1);
        sort(tmp, tmp + 4);
        bool flag = 0;
        for (int j = 0; j < 4; j++)
            if (tmp[j] != j)
                { flag = 1; break; }
        if (flag)
        {
            A.a[(i & 252) >> 2][i & 63] = 1;
            res.a[i & 63][i & 63]++;
            ans++;
        }
    }
    
    ll tot = 1, base = 4;
    for (int i = 0; i < 63 && (1ll << i) <= n; i++) {
        if (n & (1ll << i)) tot = (tot * base) % oo;
        base = (base * base) % oo;
    }
    
    n -= 4;
    for (int i = 0; i < 63 && (1ll << i) <= n; i++) {
        if (n & (1ll << i)) res *= A;
        A *= A;
    }
    printf("%lld\n", (tot - res.sum() + oo) % oo);
    return 0;
}



[CDOJ 1606] D - 难喝的饮料

Problem

两种类型饮料,一种无限,一种只有一份。每种饮料每喝一份,难受度增加 wi,愉悦度增加 pi,总难受度不能超过 K,求最大愉悦度。
n≤20000 K,wi,pi≤10000

Solution

01 背包 + 无限背包。暴力 309 MS
其实还可以做点小优化,比如对于同样难受度的饮料,按愉悦度从大到小依次 DP,遍历到一种无限饮料就直接跳过后面难受度一样的饮料。并且对于愉悦度为 0 的饮料直接跳过。113 MS

Code

const int W=11000;
int f[W];
int wei, p, c, base, weight, value, i, n, w;

int main()
{
    scanf("%d%d", &n, &w);
    while (n--)
    {
        scanf("%d%d%d", &c, &p, &wei);
        if (p == 0) continue;
        if (c == 2)
            for (i = w; i >= wei; i--)
                f[i] = max(f[i], f[i - wei] + p);
        else
            for (i = wei; i <= w; i++)
                f[i] = max(f[i], f[i - wei] + p);
    }
    int ans = 0;
    for (i = 1; i <= w; i++) ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}



[CDOJ 1652] E - 都市大飙车

Problem

一辆车行驶在 m 车道的高速路上,每行驶 1 公里汽车有 1/3 的概率向左移动一个车道,1/3 的概率停留在当前车道,1/3 的概率向右移动一个车道。当然,如果左右没有车道,就不会移动。比如说如果当前汽车在最左边的车道,并且右边有车道,那么它有 1/2 停留,有 1/2 的概率向右移动。如果左右没有车道,当然就不会换道了。
高速路上有 k 个障碍物,车辆撞上就是车毁人亡。那么车辆安全行驶 n 公里的概率是多少?
第一行三个数 m, k, n。1≤m≤30000, 0≤k≤100, 1≤n≤1000
第二行一个数 p,表示从左数第 p 道为起始车道。
接下来 k 行,每行两个数 ai, bi,表示左数第 ai 个车道距离起点 bi 公里有一个障碍物。

Solution

f[i][j] 表示到达第 i 公里第 j 个车道的概率。

对于 1<j<m, 有递推式
f[i+1][j] += f[i][j] / 3
f[i+1][j-1] += f[i][j] / 3
f[i+1][j+1] += f[i][j] / 3
对于 j=1 或者 j=m,类似处理

对于单车道 (m=1) 的情况特别处理

因为状态数过多,所以用滚动数组

并且,因为 m≤30000 n≤1000,所以实际上车辆能到达的车道只有 max(1, p-n) ~ min(m, p+n)
所以只需要枚举这个范围内的车道即可(不过测了一下完整枚举,也能过,319 MS)

时间复杂度 O(n^2) 45 MS
空间复杂度 O(m) 1336 KB

Code

const int M=30100;
const int N=1100;
double f[2][M];
int a[110], b[110];
int m, K, n, p, i, j, x, y;

int main()
{
    scanf("%d%d%d", &m, &K, &n);
    scanf("%d", &p);
    f[0][p] = 1;
    int st = max(2, p - n);
    int en = min(m - 1, p + n);
    for (i = 1; i <= K; i++) scanf("%d%d", &a[i], &b[i]);
    
    if (K == 0)
    {
        puts("1.000000");
        return 0;
    }
    if (m == 1)
    {
        bool flag = 1;
        for (i = 1; i <= K; i++)
            if (b[i] <= n) {flag = 0; break;}
        puts(flag ? "1.000000" : "0.000000");
        return 0;
    }

    for (i = 1; i <= n; i++)
    {
        y = i & 1; x = y ^ 1;
        for (j = st - 1; j <= en + 1; j++) f[y][j] = 0;
        
        f[y][1] += f[x][1] / 2.0;
        f[y][2] += f[x][1] / 2.0;
        f[y][m] += f[x][m] / 2.0;
        f[y][m - 1] += f[x][m] / 2.0;
        
        for (j = st; j <= en; j++)
        {
            f[y][j] += f[x][j] / 3.0;
            f[y][j - 1] += f[x][j] / 3.0;
            f[y][j + 1] += f[x][j] / 3.0;
        }
        
        for (j = 1; j <= K; j++)
            if (b[j] == i) f[y][a[j]] = 0;
    }
    double ans = 0;
    for (i = st - 1; i <= en + 1; i++) ans += f[n & 1][i];
    printf("%.6lf\n", ans);
    return 0;
}



[CDOJ 1271] F - Search gold

Problem

一开始在 (1,1),从 (x,y) 能跳到 (x+1,y), (x,y+1), (x+1,y+2) and (x+2,y+1)。到达一格就加上这一格的权值,整个过程权值和不能为负,求走到 (n,m) 的最大权值和
1≤n≤1000, 1≤m≤1000, |Aij|≤100

Solution

很简单的 DP,四个方向决策一下就好了。

Code

const int N=1010;
const int fx[4] = {1, 0, 1, 2};
const int fy[4] = {0, 1, 2, 1};
int i, j, k, n, m, ans, x, ma, dx, dy;
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    ans = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            int ma = -1;
            scanf("%d", &x);
            for (k = 0; k < 4; k++)
            {
                dx = i - fx[k]; dy = j - fy[k];
                if (dx > 0 && dy > 0 && f[dx][dy] >= 0)
                    ma = max(ma, f[dx][dy] + x);
            }
            if (i == 1 && j == 1) ma = x;
            f[i][j] = ma;
            ans = max(ma, ans);
        }
    
    printf("%d\n", ans);
    return 0;
}



[CDOJ 1006] G - 最长上升子序列

Problem

求最长上升子序列中最小的序列
数据组数 T<=100,序列长度 N≤1000

Solution

用传统 nlgn 的做法,因为单调队列会维护最小的性质,所以只要在 dp 完 a[i] 之后,记录下 a[i] 在单调队列中的前驱就行了

Code

int f[1010], fi[1010], pre[1010], a[1010];
int i, T, n, k, x;

int find(int l, int r, int x)
{
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (f[mid] < x)
            l = mid + 1;
        else r = mid;
    }
    return l;
}

void print(int x)
{
    if (x == 0) return;
    print(pre[x]);
    printf("%d ", a[x]);
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        int ans=0;
        for (i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            a[i] = x;
            if (x > f[ans])
            {
                f[++ans] = x;
                fi[ans] = i;
                pre[i] = fi[ans - 1];
                continue;
            }
            k = find(1, ans, x);
            f[k] = x;
            pre[i] = fi[k - 1];
            fi[k] = i;
        }
        printf("%d ", ans);
        print(fi[ans]);
        puts("");
    }
    return 0;
}



[CDOJ 1651] H - Uestc的命运之旅

Problem

给一个带权值的矩阵,两个专家分别从左上角和左下角出发,走到右下角和右上角,两人路径只有一个公共点,定义好感度为两路径权值和减掉重合部分权值。3≤n,m≤1000,0≤Aij≤10000

Solution

观察公共点前后的路径,可以发现四条路径没有交叉,各自占据四个不重叠的子矩阵,所以我们可以直接枚举公共点,问题就转化为求四个子矩阵的最大权值和路径。

Code

const int N=1010;
typedef long long ll;
ll lt[N][N], rt[N][N], ld[N][N], rd[N][N], a[N][N];
int n, m, i, j;
void dp(ll (*f)[N], int nl, int ml)
{
    int nr=(nl==1 ? n : 1), mr=(ml==1 ? m : 1);
    int dn=(nl<nr ? 1 : -1), dm=(ml<mr ? 1 : -1);
    for (int i = nl; i != nr; i += dn)
        for (int j = ml; j != mr; j += dm)
            f[i][j] = max(f[i][j-dm], f[i-dn][j]) + a[i][j];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) scanf("%lld", &a[i][j]);
    dp(lt, 1, 1); dp(rt, 1, m);
    dp(ld, n, 1); dp(rd, n, m);
    ll ans=0;
    for (i = 2; i < n; i++)
        for (j = 2; j < m; j++)
        {
            ans = max(ans, lt[i-1][j] + rt[i][j+1] + 
                           ld[i][j-1] + rd[i+1][j]);
            ans = max(ans, lt[i][j-1] + rt[i-1][j] + 
                           ld[i+1][j] + rd[i][j+1]);
        }
    printf("%lld\n", ans);
    return 0;
}



[CDOJ 1653] I - 最小生成树?

Problem

坐标平面上有 n 个点,现在我们想要把这些点连成一棵有向树。但是不幸的是,树的边只能向右或者向上长。现在我们想知道,这棵树总边长的最小值是多少。0<n≤1000,0≤xi,yi≤10000,数据保证对于所有的 i≤j,有 xi≤xj, yi≥yj
原题:HDU3516 - Tree Construction

Solution

考虑区间 DP,f[i][j] 表示将 i..j 这些点连成一片树的总边长
则 f[i][j] = f[i][k] + f[k+1][j] + x[k+1] - x[i] + y[k] - y[j]

显然 f[i][i] = 0

s[i][j] 表示最终决策 f[i][j] 的 k,定义 s[i][i] = i

对拍发现满足四边形不等式,即有 s[i][j-1] <= s[i][j] <= s[i][j+1]
所以可优化至 O(n^2)

Code

int main()
{
    while (scanf("%d", &n) > 0)
    {
        for (i = 1; i <= n; i++)
        {
            scanf("%d%d", &x[i], &y[i]);
            s[i][i] = i;
        }
        for (l = 2; l <= n; l++)
            for (i = 1; i <= n - l + 1; i++)
            {
                j = i + l - 1;
                f[i][j] = INF;
                for (k = s[i][j-1]; k <= s[i+1][j] && k < j; k++)
                {
                    int tmp = f[i][k] + f[k+1][j] + (x[k+1] - x[i] + y[k] - y[j]);
                    if (tmp < f[i][j])
                    {
                        f[i][j] = tmp;
                        s[i][j] = k;
                    }
                }
            }
        printf("%d\n", f[1][n]);
    }
    return 0;
}

Note

[HDU 3516]Tree Construction



[CDOJ 1654] J - 肆虐的病毒

Problem

你发现,你的电脑中了最近到处肆虐的一种病毒。这种病毒甚至通过一种奇怪的方法,改变了你最近晚上的入睡时间。 这种操作使你感到非常的难受,所以你向黑客发了封邮件,恳请他放你一马。
黑客告诉你,他确实可以放你一马。但是,你得和他玩一个游戏,成败全在你自己。
在这个游戏中,有以 1⋯n(2≤n≤7000) 编号的,共计 n 个物体被放置在一个圆环里面(顺时针)。编号为 1 的物体是你的女朋友。其他的都是小绿帽。游戏开始的时候,一个小机器人会被随机的放在这 n 个物体的其中的一个旁边(放心,当然不会是你的女朋友旁边)。
你和黑客手上都分别有一个数集(里面有从 1 到 n−1 的一些数字)。黑客的集合是 s1,大小是 k1,你的集合是 s2,大小是 k2。你和黑客中的一个人会走先手,之后轮流进行操作。在每个回合中,当前的玩家的意识会和小机器人进行对接,当前的的玩家可以从他的集合中任意的选择一个数 x,然后这个数可以使小机器人沿着顺时针方向走 x 步。如果当前玩家操纵小机器人到达了你的女朋友处(1 处),那么他就赢得了游戏。每走到一个不是你女朋友的位置,你就会获得一顶小绿帽。
你现在很方,你想知道对于每一种可能的开局(谁先走,机器人放在哪个位置),你的输赢情况(假设黑客和你都绝顶(秃)聪明),于是你打算编写一个程序来解决你的疑惑。要注意,有一种谁都不赢谁的方法,但是这种情况下游戏会无限的循环,这意味着你会得到无限顶小绿帽。 原题:Codeforces Round #406 (Div. 2) C - Berzerk

Solution

考虑每个点先手时的必胜/败态。 如果当前正在某个点,接下去可以走到的点全是对方的必胜点,那么这个点就是必败点,如果接下去可以走到的点中有一个是对方的必败点,那么这个点是必胜点。特别定义 1 是必败点。 但是这样子的判定肯定是有先后顺序的,所以我们要从 1 开始延展开来,将所有的必胜点和必败点加入队列中,这样 bfs 一遍就好了。

Code

const int N=7010;
int qx[N<<1], qy[N<<1];
int n, x, y, tmp, i, loc, s, t;
int tot[2], a[2][N], f[2][N];

void print(int x)
{
    for (int i = 1; i < n; i++)
        printf(f[x][i] == -1 ? "Win " : 
				(f[x][i] == tot[x] ? "Lose " : "Loop "));
    puts("");
}

int main()
{
    scanf("%d", &n);
    for (int x = 0; x < 2; x++)
    {
        scanf("%d", &tot[x]);
        for (i = 1; i <= tot[x]; i++) scanf("%d", &a[x][i]);
    }
    f[0][0] = tot[0]; f[1][0] = tot[1];
    qx[1] = 0; qy[1] = 0;
    qx[2] = 1; qy[2] = 0;
    s = 0; t = 2;
    while (s != t)
    {
        x = qx[++s];
        loc = qy[s];
        y = x ^ 1;
        for (i = 1; i <= tot[y]; i++)
        {
            tmp = (loc - a[y][i] + n) % n;
            if (f[y][tmp] >= 0 && f[y][tmp] < tot[y])
                if (f[x][loc] == tot[x])
                {
                    f[y][tmp] = -1;
                    qx[++t] = y;
                    qy[t] = tmp;
                }
                else
                {
                    f[y][tmp]++;
                    if (f[y][tmp] == tot[y])
                    {
                        qx[++t] = y;
                        qy[t] = tmp;
                    }
                }
        }
    }
    print(0);
    print(1);
    return 0;
}

Note

[Codeforces 786A]Berzerk



[CDOJ 1689] K - 分序列

Problem

将序列分组,每个组的权值为组内每个数的平方和再加上 M,求最小总权值和。0≤n≤500000, 0≤M≤1000 原题:HDU3507 - Print Article

Solution

f[i] 表示前 i 个数的最小总权值和,那么显然有
f[i] = min{f[j] + s[i] - s[j] | j=0..i-1}
这样是要超时的,大概是需要一发斜率优化

假设 j < k < i,那么 k 比 j 更优
等价于 f[j] + (s[i]-s[j])^2 + m >= f[k] + (s[i]-s[k])^2 + m
等价于 f[j] + s[j]^2 - (f[k] + s[k]^2) >= 2*s[i]*(s[j]-s[k])
显然 s[j] <= s[k],所以有

(f[j] + s[j]^2) - (f[k] + s[k]^2)
--------------------------------- <= s[i]
      2 * (s[j] - s[k])

所以将 (2*s[j], f[j]+s[j]^2) 作为一个直角坐标系上的点,那么不等式左边就表示斜率  
考虑 j, k, i 这三个点,横坐标依次增大(非降),纵坐标也依次增大(非降),形成三角形,那么有两种情况:  
一、
k 在最大边的上方。此时边 (j,k) 的斜率是三边中最大的。
如果在后面的 DP 中 k 比 j 更优,说明边 (j,k) 斜率满足不等式。
那么另两边也必定满足,说明 i 比 k 更优,所以 k 没有价值,直接舍去。
二、
k 在最大边的下方。此时斜率:(j, k) <= (k, i) <= (j, i)。
所以如果 (j,k) 满足不等式,那么说明 k 比 j 优,直接删掉 j。
如果 (k,i) 满足不等式,说明 i 比 k 优且 k 比 j 优,直接删掉 i 和 j。
(j,i) 同理。反之,如果三个斜率都不满足,说明 j 最优。

而且因为不等式右边随 i 增大而增大。
所以随着 i 增大,各个不等式一定是从不成立到成立的。也就是说后面的点只会变得更优(相对于前面的点来说)

综合以上操作可以发现,所有的点满足下凸壳的性质。
所以我们只需要根据一系列条件维护一个下凸壳,最优的就是凸壳最前面的点。

Code

typedef long long ll;
const int N=500010;
ll f[N], qx[N], qy[N], s[N], nx, ny;
int qz[N];
int i, n, m, h, t;

void read(ll &x) {...}

int main()
{
    while (scanf("%d%d", &n, &m) == 2)
    {
        for (i = 1; i <= n; i++) 
        {
            read(s[i]);
            s[i] += s[i - 1];
        }
        h = 1; t = 1;
        qx[1] = 0; qy[1] = 0; qz[1] = 0;
        for (i = 1; i <= n; i++)
        {
            // K(h, h+1) <= s[i]
            while (h < t && qy[h+1] - qy[h] <= s[i] * (qx[h+1] - qx[h])) h++;
            int j = qz[h];
            f[i] = f[j] + (s[i] - s[j]) * (s[i] - s[j]) + m;
            
            // K(t-1, t) >= K(t, new)
            nx = s[i] << 1;
            ny = f[i] + s[i] * s[i];
            while (h < t && (qy[t] - qy[t-1]) * (nx - qx[t]) >= 
                            (qx[t] - qx[t-1]) * (ny - qy[t])) t--;
            qx[++t] = nx; qy[t] = ny; qz[t] = i;
        }
        printf("%lld\n", f[n]);
    }
    return 0;
}

Note

[HDU 3507]Print Article



[CDOJ 1690] L - 这是一道比CCCC简单题难的简单题

Problem

给定一个n*m的矩阵,使用1*2的小长方形覆盖矩阵,求方案数。2≤n≤1000 3≤m≤5

Solution

与 C 题类似,用二进制表示一行的状态。 在一行的状态是 x 的情况下,如果用若干块骨牌覆盖上去,能把这一行覆盖满并且使得下一行的状态是 y 的话,那么标记 A(x,y) = 1。 初始状态就是假设第 0 行是满的,然后递推 n 次就能得到最终状态(矩阵计算 A^n 就是整个递推的过程)最后再随便推一下答案就出来了。

Code

using namespace std;
typedef long long ll;
const int N=1<<7;
const int oo=1e9+7;
int n, m, M, x, i, j;

class Matrix {
    
public:
    ll **a;
    Matrix()
    {
        a = new ll*[M];
        for (int i = 0; i < M; i++)
            a[i] = new ll[M];
    }
    void initial()
    {
        for (int row = 0; row < M; row++)
            for (int col = 0; col < M; col++)
                a[row][col] = 0;
    }
    void print()
    {
        for (int row = 0; row < M; row++)
        {
            for (int col = 0; col < M; col++)
                printf("%d ", a[row][col]);
            puts("");
        }
        puts("");
    }
    void operator*=(const Matrix &r) {
        Matrix res;
        res.initial();
        for (int row = 0; row < M; row++) {
            for (int col = 0; col < M; col++) {
                for (int k = 0; k < M; k++) {
                    res.a[row][col] += a[row][k] * r.a[k][col];
                    res.a[row][col] %= oo;
                }
            }
        }
        *this = res;
    }
};

void build(int k, int y, Matrix &A)
{
    if (k >= m)
    {
        A.a[x][y] = 1;
        return;
    }
    int b = 1 << k;
    if ((x & b) == 0)
    {
        build(k + 1, y | b, A);
        return;
    }
    build(k + 1, y, A);
    if (k < m - 1 && (x & (b << 1)) != 0)
        build(k + 2, y | b | (b << 1), A);
}

int main()
{
    scanf("%d%d", &n, &m);
    M = 1 << m;
    Matrix A;
    A.initial();
    for (i = 0; i < M; i++)
        { x = i; build(0, 0, A); }

    Matrix res;
    res.initial();
    res.a[M-1][M-1] = 1;

    for (int i = 0; i < 31 && (1 << i) <= n; i++) {
        if (n & (1 << i)) res *= A;
        A *= A;
    }
    printf("%lld\n", res.a[M-1][M-1]);
    return 0;
}

Note

[hihoCoder 1162]骨牌覆盖问题·三



[CDOJ 1691] M - 这是一道比CCCC简单题经典的中档题

Problem

N 种豆奶,每种豆奶的数量为 C1,C2 … Cn,每种豆奶的体积为 W1,W2 … Wn(Wi为整数),与之相对应的价值为 P1,P2 … Pn(Pi为整数)。
从中任选若干件放在容量为 W 的背包里,求背包能够容纳的豆奶最大价值。
1≤N≤100,1≤W≤50000,1≤Wi,Pi≤10000,1≤Ci≤200

Solution

经典背包问题,二进制拆分优化。时间复杂度 O(N W logCi)

Code

const int W=51000;
int f[W];
int wei, p, c, base, weight, value, i, n, w;

int main()
{
    scanf("%d%d", &n, &w);
    while (n--)
    {
        scanf("%d%d%d", &wei, &p, &c);
        base = 1;
        while (c >= base)
        {
            weight = base * wei;
            value = base * p;
            for (i = w; i >= weight; i--)
                f[i] = max(f[i - weight] + value, f[i]);
            c -= base;
            base <<= 1;
        }
        if (c > 0)
        {
            weight = c * wei;
            value = c * p;
            for (i = w; i >= weight; i--)
                f[i] = max(f[i - weight] + value, f[i]);
        }
    }
    int ans = 0;
    for (i = 1; i <= w; i++)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}



[CDOJ 1692] N - 这是一道比CCCC简单题更有想象力的中档题

Problem

n 个参赛队员,对于第i个队员,每写一行代码,就会留下 ai 个 bug
需要写 m 行代码,请安排各个队员写的代码行数,使得整个代码的 bug 数不超过 b 个
仅队员写代码顺序不同的两个方案属于同一种方案,只有当某个队员代码行数不同时才能算作两种方案。
求总方案数(对mod取模)。1≤n,m≤500,0≤b≤500,1≤mod≤1e9+7,0≤ai≤500

Solution

因为与顺序无关,所以一个队员只能决策一次,要以队员为阶段划分
f(i,j) 表示前 i 个队员,写了 j 行代码,存在 k 个 bug 的方案数
那么 f(i,j,k) = sum{f(i-1, j-x, k-x*a[i]) | x*a[i]<=k, x<=j}
时间复杂度 O(n^4)

考虑到每个选手可以写任意行代码,所以整个题目可以看作无限背包的模型。
把每个选手看作物品,使用无限背包的枚举顺序来优化时间复杂度和空间复杂度:

for i=1..n
    for j=1..m
        for k=a[i]..b
           f[j][k] += f[j-1][k-a[i]]

Code

int n, m, b, oo, i, j, k, y, l, a;
int f[510][510];

int main()
{
    scanf("%d%d%d%d", &n, &m, &b, &oo);
    f[0][0] = 1;
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &a);
        for (j = 1; j <= m; j++)
            for (k = a; k <= b; k++)
                f[j][k] = (f[j][k] + f[j - 1][k - a]) % oo;
    }
    int ans=0;
    for (i = 0; i <= b; i++)
        ans = (ans + f[m][i]) % oo;
    printf("%d\n", ans);
    return 0;
}






评论区加载中