题意
求长度为 $n (1 \le n \le 5000)$ 的序列中的最长严格递减子序列长度，并求不同的最长严格递减子序列的数量。
注意此处判断两个序列相同，指生成的子序列值（而非序列下标）。
思路
由于长度的最大值为 $5000$，所以可使用 $O(N^2)$ 时间复杂度求 LIS，并统计方案数。
此处对于方案数的统计，如果不考虑序列中相同的数字，则有：
1
2
3
4
5
6
7
8
9
10
11
| for(int i = 1; i <= n; i++) {
dp[i] = plan[i] = 1;
for(int j = 1; j < i; j++)
if (a[j] <= a[j]) {
if (dp[j] + 1 == dp[i]) plan[i] += plan[j];
else if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
plan[i] = plan[j];
}
}
}
|
和计数类型的动态规划类似，如果 $j$ 处值与 $i$ 处值相同，则加上 $j$ 处的方案数；如果 $j$ 处值更
优，在更新最优值的同时，也需要更新方案数。
此处需要处理相同的值序列带来的影响。考虑有 $a[i] == a[j], (j < i)$，对于 $1 \dots j-1$ 位置的子序列集合 $S$，再连接上 $a[j]$，得到方案数 $plan[j]$。此时 $S$ 后连接 $a[i]$ 得到子序列必然是重复的。因此这部分的数量不需要计入。在代码中，顺序遍历 $j$ 时，如果有 $a[i] == a[j]$，则可直接将 $plan[i]$ 的值置为 $0$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int a[N], dp[N], plan[N];
int main() {
freopen("stock.in", "r", stdin);
freopen("stock.out", "w", stdout);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) {
dp[i] = plan[i] = 1;
for(int j = 1; j < i; j++) {
if(a[i] < a[j]) {
if(dp[i] == dp[j] + 1) plan[i] += plan[j];
else if(dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
plan[i] = plan[j];
}
} else if (a[i] == a[j]) plan[i] = 0;
}
}
int mx = 0, ans = 0;
for(int i = 1; i <= n; i++) {
if(dp[i] > mx) {mx = dp[i]; ans = plan[i];}
else if(dp[i] == mx) ans += plan[i];
}
printf("%d %d\n", mx, ans);
return 0;
}
|
题意
求一个整数加法群（$n\le100$，最大元素的值不超过 $2.5\times10^4$）的子集，该子集与原加法群等价，且元素数量最少
思路
如果在这个加法群中，一个值能够被其更小的值线性表出，那么去掉该值后，群的表示能力是不变的。因此对所有群中的数排序后，依次加入独立的元素。判断该值能否被其更小的值表示出，可以使用完全背包的方式。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 3e4+5;
int a[N];
bool vis[M];
int main()
{
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
int T; scanf("%d", &T);
while(T--) {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a+1, a+n+1);
memset(vis, 0, (a[n]+1)*sizeof(bool));
vis[0] = 1;
int cnt = 0;
for(int i = 1; i <= n; i++){
if(!vis[a[i]]){
cnt++;
int bound = a[n] - a[i];
for(int k = 0; k <= bound; k++)
if(vis[k])
vis[k+a[i]] = 1;
}
}
printf("%d\n", cnt);
}
return 0;
}
|
题意
一串项链有 $n$ 颗珠子，每个珠子有头标记和尾标记，前一颗珠子的尾标记等于下一颗的头标记。如 $n = 4$ 时，珠子的例子为 $(2,3)(3,5)(5,10)(10,2)$。
相邻的珠子可以聚合并得到分数，具体的，若前一颗珠子标记为$(m, r)$，后一颗珠子标记为$(r,n)$，则进行聚合后变为一颗$(m, n)$的珠子，并得到 $m \times r \times n$的分数。求将所有珠子缩为一颗后的最大分数。对于上例，使用$(i\oplus j)$表示第$i,j$颗珠子聚合后所释放的能量，则最大为
思路
初看该问题建模比较难，主要由于两颗珠子合并之后产生的珠子，能够继续用于之后的动规过程，这为决策阶段的划分造成困难。
有一个非常类似的问题——“凸多边形最优三角划分”，三角划分指的是在多边形中连接 $n - 3$ 条不相交的对角线（弦），将多边形切成 $n - 2$ 个小三角形。而最优划分指的是，由多边形的边和弦组成的三角形的权函数之和最小（大）。
在该问题中尝试定义 dp[l][r]，为最终剩余的两颗珠子为 l 和 r 的最大能量。
易推出该动态规划的转移方程式为：
注意到如果只输出 dp[1][n] 作为结果，原先环的性质将被破坏。
此处使用对环状问题的常规处理，扩展为原先的两倍后，取 dp[i][i+n] 的最大值即可。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205;
ll a[N], dp[N][N];
int main() {
freopen("energy.in", "r", stdin);
freopen("energy.out", "w", stdout);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
a[n + i] = a[i];
}
for(int len = 3; len <= n + 1; len++) {
for(int l = 1; l + len - 1 <= 2 * n; l++) {
int r = l + len - 1;
for(int k = l + 1; k < r; k++)
dp[l][r] = max(dp[l][r],
dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
}
}
ll ans = 0;
for(int i = 1; i <= n; i++) ans = max(ans, dp[i][i + n]);
printf("%lld\n", ans);
return 0;
}
|
题意
从 $n \times m (n, m \le 10^3)$ 的方格图左上角走到右下角，每步可以向上、向下或向右走一格，不能走过已经走过的方格。求取到整数之和的最大值。
思路
从经典的只能向下向右的方格取数的拓展。回忆在经典的方格取数问题中，对于状态的定义为 dp[i][j] 表示走到第 i 行第 j 列所能够取到的最大值。则有 $dp[i][j] = \max\left\{dp[i-1][j], dp[i][j-1]\right\} + a[i][j]$。
此处需要避免某个格子重复进入的情况，假定此时的状态仍然为 dp[i][j]，则有转移方程式 $dp[i][j] = \max\left\{dp[i-1][j], dp[i][j-1], dp[i+1][j] \right\} + a[i][j]$。明显这样不能够避免重复的情况。
在无后效性条件被破坏时，一个解决方法为添加维度描述状态。
在此处使用 dp[i][j][0/1/2] 描述某个位置取到的最大和值，而 0 表示该位置从左边而来， 1, 2 表示从上面和下面而来。
由此转移方程式非常清晰：
注意边界条件，且答案仅为 $\max\left\{dp[n][m][0], dp[n][m][1]\right\}$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
ll a[N][N];
ll dp[N][N][3];
int main() {
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j];
memset(dp, 0xe0, sizeof(dp));
dp[0][1][0] = 0;
for(int j = 1; j <= m; j++) {
for(int i = 1; i <= n; i++) dp[i][j][0] = a[i][j] + max(dp[i][j - 1][0], max(dp[i][j - 1][1], dp[i][j - 1][2]));
for(int i = 1; i <= n; i++) dp[i][j][1] = a[i][j] + max(dp[i - 1][j][0], dp[i - 1][j][1]);
for(int i = n; i >= 1; i--) dp[i][j][2] = a[i][j] + max(dp[i + 1][j][0], dp[i + 1][j][2]);
}
cout << max(dp[n][m][0], dp[n][m][1]);
return 0;
}
|
题意
除某玩家外共有 s 名玩家，每位玩家共有 $m$ 名士兵，争夺 $n$ 个城堡。
玩家两两对战，且每次的策略固定。若玩家 j 的在城堡 i 派出士兵为 $a_{ij}$，曾当派出士兵数大于 $2a_{ij}$ 时，则视为控制了该城堡，获得 i 分。
若给定其他人策略，问最优策略下这位玩家的最优得分。
思路
分组背包模板。将每个城堡看作一个包，将所有的 $a_{ij}$ (i固定)升序排列后，在该城堡付出 $a_{ik}$ 的费用可以获得 i * k 的得分。该包中只能够选择一种方案。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 2e4+5;
int a[N][N];
int dp[M];
int main() {
freopen("arrange.in", "r", stdin);
freopen("arrange.out", "w", stdout);
int s, n, m; scanf("%d%d%d", &s, &n, &m);
for(int i = 1; i <= s; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &a[j][i]);
for(int i = 1; i <= n; i++) sort(a[i] + 1, a[i] + s + 1);
for(int i = 1; i <= n; i++)
for(int v = m; v >= 1; v--)
for(int k = 1; k <= s; k++)
if(v >= 2 * a[i][k] + 1)
dp[v] = max(dp[v], dp[v - (2 * a[i][k] + 1)] + i * k);
printf("%d\n", dp[m]);
return 0;
}
|