洛谷刷题杂记
目录
- useful
- \(\color{#E91}{普及-}\)
- \(\color{#FC1}{普及/提高-}\)
- \(\color{#6B1}{普及+/提高}\)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- \(\color{#115}{NOI/NOI+/CTSC}\)
- 动态规划
- \(\color{#E91}{普及-}\)
- P1115 最大子段和
- \(\color{#FC1}{普及/提高-}\)
- P1140 相似基因
- P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落
- P1775 石子合并（弱化版）
- P2340 [USACO03FALL]Cow Exhibition G
- \(\color{#6B1}{普及+/提高}\)
- CF607B Zuma
- P1541 [NOIP2010 提高组] 乌龟棋
- P1880 [NOI1995] 石子合并
- P3146 [USACO16OPEN]248 G
- P3147 [USACO16OPEN]262144 P (神奇的区间DP)
- P3205 [HNOI2010]合唱队
- P4170 [CQOI2007]涂色
- P4290 [HAOI2008] 玩具取名
- P4310 绝世好题 (带位运算)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- \(\color{#115}{NOI/NOI+/CTSC}\)
- \(\color{#E91}{普及-}\)
- 数据结构
- \(\color{#E91}{普及-}\)
- \(\color{#FC1}{普及/提高-}\)
- P1774 最接近神的人
- \(\color{#6B1}{普及+/提高}\)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- \(\color{#115}{NOI/NOI+/CTSC}\)
- 字符串
- \(\color{#E91}{普及-}\)
- \(\color{#FC1}{普及/提高-}\)
- \(\color{#6B1}{普及+/提高}\)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- \(\color{#115}{NOI/NOI+/CTSC}\)
- 图论
- \(\color{#E91}{普及-}\)
- \(\color{#FC1}{普及/提高-}\)
- \(\color{#6B1}{普及+/提高}\)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- \(\color{#115}{NOI/NOI+/CTSC}\)
- 数学
- \(\color{#E91}{普及-}\)
- \(\color{#FC1}{普及/提高-}\)
- \(\color{#6B1}{普及+/提高}\)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- \(\color{#115}{NOI/NOI+/CTSC}\)
- 奇怪的题目
- \(\color{#E91}{普及-}\)
- \(\color{#FC1}{普及/提高-}\)
- \(\color{#6B1}{普及+/提高}\)
- \(\color{#48D}{提高+/省选-}\)
- \(\color{#83C}{省选+/NOI-}\)
- null
useful
\(\color{#E91}{普及-}\)
\(\color{#FC1}{普及/提高-}\)
\(\color{#6B1}{普及+/提高}\)
\(\color{#48D}{提高+/省选-}\)
\(\color{#83C}{省选+/NOI-}\)
\(\color{#115}{NOI/NOI+/CTSC}\)
动态规划
\(\color{#E91}{普及-}\)
P1115 最大子段和
水, 最基础线性DP
传送门
Solution
#include
typedef long long ll;
#define endl "\n"
using namespace std;
const int N = 2e5 + 10;
int f[N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector a(n + 1, 0);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++){
f[i] = max(a[i], f[i - 1] + a[i]);
}
int mx = -2e9;
for(int i = 1; i <= n; i++)
mx = max(mx, f[i]);
cout << mx << endl;
return 0;
}
\(\color{#FC1}{普及/提高-}\)
P1140 相似基因
典中典双序列匹配问题, 可能书中放在区间DP感觉怪怪的
传送门
思路
- 就按照最长公共子序列的状态定义方式就好了
- 然后很容易的就能写出状态转移方程了
Solution
#include
typedef long long ll;
#define endl "\n"
using namespace std;
const int N = 110;
unordered_map mp;
int d[6][6], f[N][N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
mp['A'] = 1, mp['C'] = 2, mp['G'] = 3, mp['T'] = 4;
d[1][1] = 5, d[1][2] = -1, d[1][3] = -2, d[1][4] = -1, d[1][5] = -3,
d[2][1] = -1, d[2][2] = 5, d[2][3] = -3, d[2][4] = -2, d[2][5] = -4,
d[3][1] = -2, d[3][2] = -3, d[3][3] = 5, d[3][4] = -2, d[3][5] = -2,
d[4][1] = -1, d[4][2] = -2, d[4][3] = -2, d[4][4] = 5, d[4][5] = -1,
d[5][1] = -3, d[5][2] = -4, d[5][3] = -2, d[5][4] = -1;
int n, m;
string s1, s2;
cin >> n >> s1 >> m >> s2;
s1 = " " + s1;
s2 = " " + s2;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if(!i && !j){
f[i][j] = 0;
continue;
}
if(i && j)
f[i][j] = max({f[i - 1][j - 1] + d[mp[s1[i]]][mp[s2[j]]], f[i - 1][j] + d[mp[s1[i]]][5], f[i][j - 1] + d[5][mp[s2[j]]]});
if(!i)
f[i][j] = f[i][j - 1] + d[5][mp[s2[j]]];
if(!j)
f[i][j] = f[i - 1][j] + d[mp[s1[i]]][5];
}
}
cout << f[n][m] << endl;
return 0;
}
P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落
两种解法, 一个区间DP, 一个做反串后求两串LCS
题意
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。
比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。
注：此问题区分大小写
数据范围
\(0\leq |s| \leq 1000\)
思路
- 线性dp很难搞, 考虑区间DP
- 状态: \(f[i][j]\) 表示子区间 \([i,j]\) 变成回文串最小次数
- 转移:
f[l][r] = min(f[l+1][r],f[l][r-1]) + 1, if(s[l] == s[r]) f[l][r] = min(f[l][r], f[l + 1][r - 1])
#include
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair PII;
typedef std::pair PLL;
typedef double db;
#define arr(x) (x).begin(),(x).end()
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
int f[1010][1010];
// f[l][r] 表示 将区间[l,r] 变成回文串的最小次数，然后有类似有 LCS 那样的状态转移
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string s;
cin >> s;
int n;
n = s.size();
s = " " + s;
for(int len = 1; len <= n; len ++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
f[l][r] = min(f[l + 1][r], f[l][r - 1]) + 1;
if(s[l] == s[r]){
f[l][r] = min(f[l][r], f[l + 1][r - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
P1775 石子合并（弱化版）
区间DP 模板题
传送门
#include
#define endl "\n"
using namespace std;
const int N = 310;
int f[N][N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector a(n + 1, 0);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
a[i] = a[i - 1] + a[i];
memset(f, 0x3f, sizeof f);
for(int len = 1; len <= n; len ++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(len == 1){
f[l][r] = 0;
continue;
}
for(int k = l; k < r; ++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
}
}
cout << f[1][n] << endl;
return 0;
}k
P2340 [USACO03FALL]Cow Exhibition G
有趣的寻找答案方式, 背包体积为负数, 滚动数组正序枚举
题意
奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 \(N\) 头奶牛进行了面试，确定了每头奶牛的智商 \(S_i\) 和情商 \(F_i\)。
贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。
数据范围
\(-1000\leq S_i,F_i\leq 1000\)
\(n\leq400\)
思路
- 毫无疑问考虑01背包求解, 如何表示状态
f[i][?], 阶段很明确选到第 i 头牛, 第二维直接采用 情商加智商和 实际上不好解决问题.- 考虑将两个限制变为一个限制, 即 \(f[i][j]\) 表示到第 i 头牛, 情商/智商为 j 的智商/情商和最大值, 那么最后遍历一遍
max(f[n][j] + j)即可 - 细节: 智商存在负数, 智商和平移, 并且背包体积有负数时, 滚动数组需要正序枚举.
Solution
#include
#define s first
#define f second
#define endl "\n"
using namespace std;
const int N = 8e5;
int f[N + 10], n;
PII cow[410];
// 目标答案并不一定使用一个维度就能表示出来，A + B 的最大和， 可以记录 A 的最大值， 最后遍历状态值 + B 找到 A+B 最大值
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> cow[i].s >> cow[i].f;
memset(f, -0x3f, sizeof f);
f[N / 2] = 0;
for(int i = 1; i <= n; i++){
if(cow[i].s >= 0)
for(int j = N; j >= cow[i].s; j--){
f[j] = max(f[j - cow[i].s] + cow[i].f , f[j]);
}
else
for(int j = 0; j <= N + cow[i].s; j++) // 体积为负，需要正序枚举，注意背包大小
f[j] = max(f[j], f[j - cow[i].s] + cow[i].f);
}
int ans = 0;
for(int i = N / 2; i <= N; i++){
if(f[i] >= 0)
ans = max(ans, f[i] + i - N / 2);
}
cout << ans << endl;
return 0;
}
\(\color{#6B1}{普及+/提高}\)
CF607B Zuma
经典区间DP, 左右端点相同, 如果内部是回文串, 转移是没有代价的, 处理一下边界
传送门
#include
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair PII;
typedef std::pair PLL;
typedef double db;
#define arr(x) (x).begin(),(x).end()
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 510;
int f[N][N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector a(n + 1, 0);
for(int i = 1; i <= n; i++)
cin >> a[i];
memset(f, 0x3f, sizeof f);
for(int len = 1; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(a[l] == a[r]){
f[l][r] = (len <= 2) ? 1 : min(f[l][r], f[l + 1][r - 1]);
}
for(int k = l; k < r; k++)
f[l][r] = mn(f[l][r], f[l][k] + f[k + 1][r]);
}
}
cout << f[1][n] << endl;
return 0;
}i
P1541 [NOIP2010 提高组] 乌龟棋
很有意思的状态表示与转移
题意
乌龟棋的棋盘是一行 \(N\) 个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第 \(N\) 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中 \(M\) 张爬行卡片，分成4种不同的类型（\(M\) 张卡片中不一定包含所有
4种类型的卡片，见样例），每种类型的卡片上分别标有1,2,3,4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
数据范围
\(1\leq N \leq 350\)
\(1\leq M \leq 120\)
\(每种卡片最多40个\)
思路
- 重点在于状态的表示:
f[i][j][k][l]表示已经消耗了 i, j, k, l 张1,2,3,4数字的卡片的最大得分. - 值得一提的是, 此题没有明显的阶段标志, 重点在状态转移, 循环顺序上, 符合 dp 要求.
f[0][0][0][0] = a[1]起点状态, 状态转移f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l], f[i][j - 1][k][l], f[i][j][k - 1][l], f[i][j][k][l - 1] + a[1 + i+2*j+3*k+4*l])
Solution
#include
#define endl "\n"
using namespace std;
int f[41][41][41][41]; // f[i][j][k][l] 表示 消耗i张1，j张2，k张3，l张4, 最大积分
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector a(n + 1, 0);
vector b(4, 0);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 0; i < m; i++){
int x;
cin >> x;
b[x - 1] ++;
}
f[0][0][0][0] = a[1]; // 初始在 a[1] 位置
for(int i = 0; i <= b[0]; i++)
for(int j = 0; j <= b[1]; j++)
for(int k = 0; k <= b[2]; k++)
for(int l = 0; l <= b[3]; l++){
int idx = 1 + i + 2 * j + 3 * k + 4 * l; // 最终位置等于跳跃距离 + 1（起点）
if(idx > n) continue;
if(i)
f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[idx]);
if(j)
f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[idx]);
if(k)
f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[idx]);
if(l)
f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[idx]);
}
cout << f[b[0]][b[1]][b[2]][b[3]] << endl;
return 0;
}
P1880 [NOI1995] 石子合并
经典环形区间DP, 破环成链, 复制一次区间接在后面, 区间长度依然为 n
传送门
Solution
#include
#define endl "\n"
using namespace std;
const int N = 410, INF = 0x3f3f3f3f;
int w[N], n, s[N];
int f[N][N], g[N][N];
// 两条相同的链模拟环
// 状态表示： f[l][r] 表示从区间 l 到 区间 r 的最小合并费用
// 状态转移： f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> w[i];
w[i + n] = w[i];
}
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for(int i = 1; i <= 2 * n; i++)
s[i] = s[i - 1] + w[i];
for(int len = 1; len <= n; len++)
for(int l = 1; l + len - 1 <= 2 * n; l++){
int r = l + len - 1;
if(r > 2 * n) break;
if(len == 1) f[l][r] = g[l][r] = 0;
else
for(int k = l; k <= r; k++){
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
int max_ = -INF, min_ = INF;
for(int i = 1; i <= n; i++){
max_ = max(max_, g[i][i + n - 1]); // 长度为n的区间，端点差为len - 1
min_ = min(min_, f[i][i + n - 1]);
}
cout << min_ << endl << max_;
return 0;
}
P3146 [USACO16OPEN]248 G
和下一题只有数据范围不同, 多了一个区间DP的解法
题意
给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问序列中出现的最大数字的值最大是多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。
数据范围
\(1\leq n \leq 248\)
思路
- 区间DP, 定义 \(f[l][r]\) 表示 [l,r] 内合成的最大数
- 转移:
if(f[l][k] == f[k + 1][r] && f[l][k]) f[l][r] = max(f[l][r], f[l][k] + 1), 答案取每个状态最大值
Solution
#include
typedef long long ll;
#define endl "\n"
using namespace std;
const int N = 250;
int f[N][N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i++){
cin >> f[i][i];
ans = max(f[i][i], ans);
}
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(f[l][k] == f[k + 1][r] && f[l][k]){
f[l][r] = max(f[l][r], f[l][k] + 1);
ans = max(ans, f[l][r]);
}
}
}
}
cout << ans << endl;
return 0;
}
P3147 [USACO16OPEN]262144 P (神奇的区间DP)
很有趣的状态定义, 转移和倍增的感觉类似, 还是很神奇的一个区间DP
题意
她被她最近玩的一款游戏迷住了，游戏一开始有 \(n\) 个正整数，\((2\leq n\leq262144)\) ，\(a_i\) 范围在 \(1-40\) 。在一步中，贝西可以选相邻的两个相同的数，
然后合并成一个比原来的大一的数（例如两个7合并成一个8)，目标是使得最大的数最大，请帮助Bessie来求最大值。
思路
- 嗯, DP 题, 然后就不知道咋做了, 可以算出来最大答案为 \(40 + log_2262144 = 58\)
- 状态: \(f[i][j]\) 表示从 j 开始, 能合并到 i 的区间长度,
f[a[i]][i] = 1 - 转移: \(f[i][j] = f[i - 1][j] + f[i - 1][j + f[i - 1][j]]\), 后者均存在, 有点类似倍增
- 总的来说, 就是很奇怪, 多见吧
#include
#define endl "\n"
using namespace std;
const int N = 3e5;
int f[60][N]; // f[i][j] 从 j 开始合并到的数为 i 的区间长度
// f[i][j] = f[i - 1][j] + f[i - 1][j + f[i - 1][j]];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector a(n + 1, 0);
for(int i = 1; i <= n; i++){
cin >> a[i];
f[a[i]][i] = 1;
}
int ans = 0;
for(int i = 2; i <= 58; i++){
for(int j = 1; j <= n; j++){
if(!f[i][j]){
if(f[i - 1][j] && f[i - 1][j + f[i - 1][j]])
f[i][j]= f[i - 1][j] + f[i - 1][j + f[i - 1][j]];
}
if(f[i][j])
ans = i;
cout << i << " " << j << " " << f[i][j] << endl;
}
}
cout << ans << endl;
return 0;
}
P3205 [HNOI2010]合唱队
传统区间DP多加了维度
题意
太长, 给一个传送门
思路
- 由于每进来一次, 都是队列的一个扩展, 和区间DP很类似, 可以用区间DP来思考
- 套路的记录
f[l][r]表示排好区间 [l,r] 的方案数, 但我们发现, 在新加一个数还与上一次加的数有关, 还需要加维度 - 如何知道上次加的数是什么? 只有两种情况, 在左边或者在右边, 至于最里面的是怎么加的我们已经不用思考了(无后效性)
- 故多加一维
f[l][r][0/1], 0 表示最后一个数从左边加入, 1 表示最后一个数从右边加入, 判断一下各自大小, 然后很容易写出转移方程, 具体看代码
Solution
#include
#define endl "\n"
using namespace std;
const int mod = 19650827;
int f[1010][1010][2];
// f[l][r][0] 表示从左边进， f[l][r][1] 表示从右边进
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector a(n + 1, 0);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int len = 1; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(l == r){
f[l][r][0] = 1;
continue;
}
if(a[l] < a[l + 1]) f[l][r][0] += f[l + 1][r][0];
if(a[l] < a[r]) f[l][r][0] += f[l + 1][r][1];
if(a[r] > a[l]) f[l][r][1] += f[l][r - 1][0];
if(a[r] > a[r - 1]) f[l][r][1] += f[l][r - 1][1];
f[l][r][0] %= mod;
f[l][r][1] %= mod;
}
}
cout << (f[1][n][0] + f[1][n][1]) % mod << endl;
return 0;
}
P4170 [CQOI2007]涂色
一道比较常规的区间DP
题意
假设你有一条长度为 5 的木板，初始时没有涂过任何颜色。你希望把它 5 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 5 的字符串表示这个目标：RGBGR。
每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 RRRRR，第二次涂成
RGGGR，第三次涂成 RGBGR，达到目标。
用尽量少的涂色次数达到目标。
数据范围
\(1\leq n \leq 50\)
思路
- 区间DP的方式去思考, 定义 \(f[l][r]\) 为染色区间[l,r]最小次数.
- 然后根据题目性质搞一下状态转移吧,
像我这种废物只能写70分
#include
typedef long long ll;
#define endl "\n"
using namespace std;
const int N = 53;
int f[N][N][2]; // 0 left 1 right
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
string s;
cin >> s;
n = s.size();
s = " " + s;
memset(f, 0x3f, sizeof f);
for(int len = 1; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(l == r){
f[l][r][0] = 1;
continue;
}
f[l][r][0] = min(f[l][r][0], f[l + 1][r][0] + (s[l] != s[l + 1]));
f[l][r][0] = min(f[l][r][0], f[l + 1][r][1] + (s[l] != s[r]));
f[l][r][1] = min(f[l][r][1], f[l][r - 1][0] + (s[l] != s[r]));
f[l][r][1] = min(f[l][r][1], f[l][r - 1][1] + (s[r] != s[r - 1]));
if(s[l] == s[r]){
f[l][r][0] = min(f[l]r][0], f[l + 1][r - 1][0] + (s[l] != s[l + 1]));
f[l][r][1] = min(f[l][r][1], f[l + 1][r - 1][0] + (s[l] != s[l + 1]));
f[l][r][0] = min(f[l][r][0], f[l + 1][r - 1][1] + (s[l] != s[r - 1]));
f[l][r][0] = min(f[l][r][0], f[l + 1][r - 1][1] + (s[l] != s[r - 1]));
}
}
}
cout << min(f[1][n][0], f[1][n][1]) << endl;
return 0;
}
P4290 [HAOI2008] 玩具取名
区间DP, 硬找状态表示
传送门
思路
- 一个字母变两个字母, 是一个向左右扩张的模型, 考虑区间DP
- \(f[l][r][a]\) 表示在区间[l,r]能否变成编号 a 的字母,
if(f[l][k][a] && f[k + 1][r][b] && ok[a][b][c]) f[l][r][c] = 1;
Solution
#include
typedef long long ll;
#define endl "\n"
using namespace std;
const int N = 210;
int f[N][N][4];
bool ok[4][4][4];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
unordered_map mp;
mp['W'] = 0, mp['I'] = 1, mp['N'] = 2, mp['G'] = 3;
int cnt[4];
for(int i = 0; i < 4; i++)
cin >> cnt[i];
for(int i = 0; i < 4; i++){
for(int j = 0; j < cnt[i]; j++){
string s;
cin >> s;
ok[mp[s[0]]][mp[s[1]]][i] = true;
}
}
string s;
cin >> s;
int n = s.size();
vector v(n + 1, 0);
for(int i = 0; i < n; i++)
v[i + 1] = mp[s[i]];
for(int len = 1; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(l == r){
f[l][r][v[l]] = 1;
continue;
}
for(int k = l; k < r; k++){
for(int c = 0; c < 4; c++)
for(int a = 0; a < 4; a++)
for(int b = 0; b < 4; b++)
if(f[l][k][a] && f[k + 1][r][b] && ok[a][b][c])
f[l][r][c] = 1;
}
}
}
bool st[4] = {false}, fl = false;
for(int i = 0; i < 4; i++){
if(f[1][n][i])
fl = true, st[i] = true;
}
if(!fl)
cout << "The name is wrong!\n";
else{
string t = "WING";
for(int i = 0; i < 4; i++){
if(st[i]){
cout << t[i];
}
}
}
return 0;
}
P4310 绝世好题 (带位运算)
非常不错的在位运算基础上的 DP
题意
给一个长度为 \(n\) 的序列 \(a\), 求 \(a\) 的子序列 \(b\) 最长长度, 满足 \(b_i\&b_{i-1} \ne 0\), 其中 \(2\leq i \leq k\)
数据范围
\(1\leq n\leq 100000\)
\(a_i\leq 10^9\)
思路
- 根据 \(b\) 的每一个数只跟前一个数有关, 根据数据大小设置状态
dp[32], \(dp[i]\) 表示最后一个元素 i 位为 1 的最长序列长度- 对于 \(a_i\) 来说, 只有该位为 1 时, 才能够对状态进行转移, 先取能够更新的最大值, 然后更新到能更新的状态上.
Solution
#include
#define endl "\n"
using namespace std;
int dp[32]; // 到了第 i 位， dp[j] j 位为1的最大序列长度
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector a(n + 1, 0);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++){
int k = 1;
for(int j = 0; j < 32; j++){
if(a[i] >> j & 1) // 可以转移，记录最大值
k = max(k, dp[j] + 1);
}
for(int j = 0; j < 32; j++)
if(a[i] >> j & 1) // 更新所有状态
dp[j] = k; // max(k, dp[j]);
}
int mx = 0;
for(int i = 0; i < 32; i++)
mx = max(mx, dp[i]);
cout << mx << endl;
return 0;
}
\(\color{#48D}{提高+/省选-}\)
\(\color{#83C}{省选+/NOI-}\)
\(\color{#115}{NOI/NOI+/CTSC}\)
数据结构
\(\color{#E91}{普及-}\)
\(\color{#FC1}{普及/提高-}\)
P1774 最接近神的人
简单题, 一个结论, 通过相邻交换使得数列递增的最小操作次数是数列中的逆序对个数
传送门
Solution
#include
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair PII;
typedef std::pair PLL;
typedef double db;
#define arr(x) (x).begin(),(x).end()
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
template
struct BIT {
int n;
vector B;
BIT(){};
BIT(int _n) : n(_n), B(_n + 1, 0) {}
void init(int _n){
n = _n;
B.resize(_n + 1);
}
inline int lowbit(int x) { return x & (-x); }
void add(int x, T v) {
for(int i = x; i <= n; i += lowbit(i)) B[i] += v;
}
T ask(int x) {
T res = 0;
for(int i = x; i; i -= lowbit(i)) res += B[i];
return res;
}
};
vector alls;
int find(ll x){
return lower_bound(arr(alls), x) - alls.begin() + 1;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
BIT bt(n);
ll ans = 0;
vector a;
for(int i = 0; i < n; i++){
ll x;
cin >> x;
a.pb(x), alls.pb(x);
}
sort(arr(alls));
alls.erase(unique(arr(alls)), alls.end());
for(int i = 0; i < n; i++){
a[i] = find(a[i]);
ans += i - bt.ask(a[i]);
bt.add(a[i], 1);
}
cout << ans << endl;
return 0;
}