P3146 [USACO16OPEN] 248 G
我们可以想到用区间DP来做
\(f_{l,r}\) 表示 \([l,r]\) 的区间内其中合并能获得的最大分值
我们要枚举区间断点 \(k\) ，然后我们来看一下在如何的情况下我们可以转移
-
\(f_{l,k}=f_{k+1,r}\) 因为想要合并左右区间两边必须相等
-
\(f_{l,k} ≠ 0\) 因为两个不存在的东西不能合并
状态转移方程
\[f_{l,r}=\max(f_{l,k},f_{k+1,r})
\]
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N], n, a[N], ans = 0;
inline int read()
{
int x = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9')
{
if (s == '-')
f = -f;
s = getchar();
}
while (s >= '0' && s <= '9')
{
x = (x << 3) + (x << 1) + (s ^ 48);
s = getchar();
}
return x * f;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ans = max(ans, a[i]);
dp[i][i] = a[i];
}
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
for (int k = l; k < r; k++)
{
if (dp[l][k] == dp[k + 1][r] && dp[l][k])
{
dp[l][r] = max(dp[l][r], dp[l][k] + 1);
ans = max(ans, dp[l][r]);
}
}
}
}
cout << ans << endl;
return 0;
}
P4084 [USACO17DEC] Barn Painting G
\(f_{i,1\to3}\) 表示选 \(i\) 且第 \(i\) 个上色为 \(j\) 的所有方案数
对于所有的初始节点 \(f_{i,1}=f_{i,2}=f_{i,3}=1\) 因为放一个数算一种方案
然后当某个节点被指定上色，其余另两位颜色的方案数为 \(0\)
例如：如果被指定上色为 \(1\) \(f_{i,2}=f_{i,3}=0\)
对于每个子节点来说，都不可以与父节点相同
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, M = N * 2, MOD = 1e9 + 7;
typedef long long LL;
int n, k, ans;
int h[M], ne[M], e[M], f[M][4], idx; // w代表可能性
int add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa)
{
for (int i = 1; i <= 3; i++)
{
if (f[u][i])
{
for (int j = 1; j <= i; j++)
f[u][j] = 0;
}
f[u][i] = 1;
}
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j != fa)
{
dfs(j, u);
//因为父节点和子节点所用的颜色不能相同,乘法原理
f[u][1] = f[u][1] * (f[j][2] + f[j][3] % MOD) % MOD;
f[u][2] = f[u][2] * (f[j][1] + f[j][3] % MOD) % MOD;
f[u][3] = f[u][3] * (f[j][1] + f[j][2] % MOD) % MOD;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> k;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for (int i = 1; i <= k; i++)
{
int a, k;
cin >> a >> k;
f[a][k] = 1;
}
dfs(1, 0);
cout << (f[1][1] + f[1][2] + f[1][3]) % MOD;//因为我们先递归后计算
//所以算到f[1][...]时已是最后计算的
return 0;
}
P8801 [蓝桥杯 2022 国 B] 最大数字
这道题我们可以想到贪心的思想
如果能成为 \(9\) 就尽量成为 \(9\) ，如果不能成为的话就尽量将数字变大
所以我们有 \(4\) 种情况
-
如果两种操作都可以变成 \(9\) ,那么两种都试试
-
如果只有第一种操作能变成 \(9\) ，那么就用第一种
-
如果只有第二种操作能变成 \(9\) ，那么就用第二种
-
如果不行，就用光第一次操作，将这一位变得尽量大
因为是暴力搜索每一个数位，设位数为 \(x\) ，时间复杂度为 \(2^x\)
#include <bits/stdc++.h>
using namespace std;
string s, ans;
int n, a, b;
//第k位,atim表示用了几次1操作,btim表示用了几次2操作,now表示目前的字符串
void dfs(int k, int atim, int btim, string now)
{
if (k == n)
{
if (now > ans) //选择最优解
ans = now;
return;
}
int x = 9 - (now[k] - '0'), y = now[k] - '0' + 1; // x和y表示几次能变成9
if (atim + x <= a && btim + y <= b) //如果两个都能变成9
{
//两个都试一试
now[k] = '9';
dfs(k + 1, atim + x, btim, now);
dfs(k + 1, atim, btim + y, now);
}
else if (atim + x <= a) //如果操作1能变成9
{
now[k] = '9';
dfs(k + 1, atim + x, btim, now);
}
else if (btim + y <= b) //如果操作2能变成9
{
now[k] = '9';
dfs(k + 1, atim, btim + y, now);
}
else //如果都不能
{
//把操作1用完
now[k] += a - atim;
dfs(k + 1, a, btim, now);
}
}
int main()
{
cin >> s >> a >> b;
n = s.size();
dfs(0, 0, 0, s);
cout << ans << endl;
return 0;
}