「AT1724」「CODE FESTIVAL 2015 OKINAWA OPEN」Beware of the Sogginess!

AutumnKite

题解AtCoderCODE FESTIVAL 2015 OKINAWA OPEN

发布于：2019年2月9日

题意

给定 \(n\) 个二元组 \((a_i,b_i)\)。一个二元组 \((a,b)\) 可以变为 \((a+t,b-t)\ (0\le t\le b)\)。你现在可以选择一些二元组并将它们分别进行（即互相独立）一次变换，使得变换后你选择的所有二元组 \((a_j,b_j)\)，\(\sum a_j\ge A,\sum b_j\ge B\)。求最少需要选择并变换的二元组数量。

\(1\le n\le 50,1\le A,B,a_i,b_i\le 10^4\)

题解

转化题意：给定 \(n\) 个二元组 \((b_i,a_i+b_i)\)，选择最少的二元组使得所有选择的二元组 \(\sum b_j\ge B,\sum (a_j+b_j)\ge A+B\)。

于是就可以 DP 了。\(dp_{i,j}\) 表示选择 \(i\) 个二元组，\(\sum b_i=j\) 时，\(\sum (a_i+b_i)\) 的最大值。

考虑把 \(n\) 个二元组依次加入，DP 方程很容易写出。

发现直接写，第二维有百万级别，怎么办？\(j>B\) 的状态都合并到 \(j=B\) 处即可。

代码

#include <bits/stdc++.h>
int n, A, B, a[55], b[55], dp[55][10005];
void cmx(int &x, int y){ x = std :: max(x, y); }
int main(){
    scanf("%d%d%d", &n, &B, &A), B += A; // 与上面的 A,B 有区别，注意区分
    for (register int i = 1; i <= n; ++i) scanf("%d%d", b + i, a + i), b[i] += a[i]; // 与上面的 ai,bi 有区别，注意区分
    memset(dp, -1, sizeof dp), dp[0][0] = 0;
    for (register int i = 1; i <= n; ++i) // 依次加入
        for (register int j = i - 1; ~j; --j) // 倒着做，与 01 背包同理
            for (register int k = 0; k <= A; ++k)
                if (~dp[j][k]) cmx(dp[j + 1][k + a[i] > A ? A : k + a[i]], dp[j][k] + b[i]);
    for (register int i = 1; i <= n; ++i) if (dp[i][A] >= B) return printf("%d\n", i), 0;
    return printf("-1\n"), 0;
}

更新于：2020年3月26日

「AT1725」「CODE FESTIVAL 2015 OKINAWA OPEN」Cat versus Wolf

题目传送门题意给定一个初始状态如图所示的建筑，共 \(n\) 层（不包括 Daruma），自底向上编号 \(1\sim n\)。下图分别表示建筑的初始状态、奇数层的放置和偶数层的放置...

「AT1723」「CODE FESTIVAL 2015 OKINAWA OPEN」Automatic Map Generator

题目传送门题意构造一张 \(H\times W\) 的由岛屿#、海洋.组成的地图，岛屿为八连通，满足恰好包含 \(K\) 个联通块。 \(1\le H,W\le 100,1\le K\...