子序列
Solution
设 (f_{i,j}) 表示以 (i) 结尾的一组选择了 (j) 个数，剩下的也能凑出一组时，剩下一组结尾数的最小值。
当 (a_{i+1}>a_i) 时，(i) 与 (i+1) 可以分到一组，因此 (f_{i+1,j}=max(f_{i+1,j},f_{i,j}))
当 (a_{i+1}>f_{i,j}) 时，(i+1) 能分到剩下的一组，该组原有 (j-i) 个数，因此 (f_{i+1,j}=max(f_{i+1,j},a_i))
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2333;
int n, a[N], f[N][N];
int main()
{
while(cin >> n)
{
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(f, 0x3f, sizeof(f));
f[1][1] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
if(f[i][j] != 0x3f3f3f3f)
{
if(a[i] < a[i + 1])
f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
if(a[i + 1] > f[i][j])
f[i + 1][i - j + 1] = min(f[i + 1][i - j + 1], a[i]);
}
if(f[n][n / 2] != 0x3f3f3f3f) printf("Yes!
");
else printf("No!
");
}
return 0;
}
塔
Solution
设 (f_{i,j}) 表示前 (i) 个积木搭成的左塔和右塔差为 (j) 时，左边的塔的最大高度
(1.) 不放如当前积木
(f_{i,j}=max(f_{i,j},f_{i-1,j}))
(2.) 当前积木放在左边
(f_{i,j}=max(f_{i,j},f_{i-1,j-a_i}+a_i))
(3.) 当前积木放在右边
(f_{i,j}=max(f_{i,j},f_{i-1,j+a_i}))
注意：
(1.) 差值可能为负数，根据数据范围，(j) 直接加上 (500000)
(2.) 注意内存，使用滚动数组优化
Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int p = 500000;
int n, Ans = 0, a[51], f[2][1000001];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(f, -0x3f, sizeof(f));
f[0][p] = 0;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 1000000; j++)
{
f[i & 1][j] = max(f[i & 1][j], f[(i & 1) ^ 1][j]);
if(j - a[i] >= 0)
f[i & 1][j] = max(f[i & 1][j], f[(i & 1) ^ 1][j - a[i]] + a[i]);
if(j + a[i] <= (p << 1))
f[i & 1][j] = max(f[i & 1][j], f[(i & 1) ^ 1][j + a[i]]);
if(j == p) Ans = max(Ans, f[i & 1][p]);
}
if(Ans != 0) printf("%d", Ans);
else printf("-1");
return 0;
}
CSP2019 括号树
Solution
历年真题，WA 到生活不能自理
首先考虑链的情况，若当前走到 (x) ((s_x==')'))，计算以当前位置为结尾的合法括号串个数记为 (f_x)。
首先不考虑多个合法括号串并列的情况，这样的括号串有且仅有一个。用栈维护与其配对的前括号 (y)，(x) 与 (y) 之间组成一个单独的以 (x) 为结尾的合法括号串 (S)，因此 (f_x++)；若考虑并列情况，每一个以 (y-1) 为结尾的合法括号串都可以与 (S) 并列形成一个新的合法括号串，(f_x+=f_{fa_y})。综上 (f_x=f_{fa_y}+1)。
用 (sum_x) 表示走到 (x) 时所有的合法括号串，则 (sum_x=sum_{fa_x}+f_x)。树上的情况也大致相同，一定要注意回溯的写法（非这样写不可，否则会 WA 到起飞）
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2333333;
struct edge { long long nxt, to; } e[N];
long long n, Ans = 0, st[N], sum[N], head[N], f[N], fa[N], top = 0, cnt = 0;
char s[N];
void add(long long x, long long y)
{
e[++cnt] = (edge) { head[x], y };
head[x] = cnt;
}
void dfs(long long x)
{
long long y = 0;
if(s[x] == '(') st[++top] = x;
else if(top)
{
y = st[top--];
f[x] = f[fa[y]] + 1;
}
sum[x] = sum[fa[x]] + f[x];
Ans ^= sum[x] * x;
for(long long i = head[x]; i; i = e[i].nxt) dfs(e[i].to);
if(s[x] == '(') top--;
else if(y) st[++top] = y;
}
int main()
{
scanf("%lld", &n);
memset(sum, 0, sizeof(sum));
memset(f, 0, sizeof(f));
memset(head, 0, sizeof(head));
for(long long i = 1; i <= n; i++) cin >> s[i];
for(long long i = 2; i <= n; i++)
{
cin >> fa[i];
add(fa[i], i);
}
dfs(1);
printf("%lld", Ans);
return 0;
}
一本通高手训练 软件开发
Solution
不想写了抄题解罢...（其实是写不好）
考虑二分答案 (mid)，原问题变为判定是否存在一种方案，在给定天数内使得两个软件都能至少被完成 (m) 个模块。
我们设 (f_{i,j}) 表示已经处理到第 (i) 个技术人员，第一个软件完成 (j) 个模块时第二个软件最多能完成多少个模块，则状态转移方程为：
(f_{i,j}=max(f_{i-1,j-k}+frac{mid-k*d1_i}{d2_i}))
表示第 (i) 个技术人员第一个软件完成 (k) 个模块，则第二个软件最多完成 (frac{mid-k*d1_i}{d2_i}) 个模块。
最后若 (f_{n,m}>=m) 则答案合法，时间复杂度为 (O(nm^2log_{nm}))
注意边界！
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1100;
int n, m, Ans, l = 0, r = 0, d1[N], d2[N], f[N][N];
bool check(int x)
{
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 1; k <= j && k * d1[i] <= x; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k] + (x - k * d1[i]) / d2[i]);
if(f[n][m] >= m) return true;
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &d1[i], &d2[i]);
r += d1[i] * m + d2[i] * m;
}
while(l + 1 < r)
{
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid;
}
if(check(l)) Ans = l;
else Ans = r;
printf("%d", Ans);
return 0;
}