CF
Problem - 137D - Codeforces
区间dp+分段dp
暴力修改字符串形成回文串，求得到不超过 \(k\) 个字符串的最小花费
训练码力的好题
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair<int, int>
const LL mod = 998244353;
const int N = 510;
int cost[N][N], dp[N][N];
string s;
int n;void Print(int now,int num){if(now==0||num==0)return;for (int i = 0; i < now;i++){if(dp[i][num-1]+cost[i+1][now]==dp[now][num]){Print(i, num - 1);int len = now - (i + 1) + 1;for (int j = i + 1; j <= i + 1 + len / 2 - 1;j++){s[j] = s[now - (j - i - 1)];}for (int j = i + 1; j <= now;j++){cout << s[j];}if(now!=n){cout << "+";}break;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int K;cin >> s >> K;n = s.size();s = " " + s;for (int len = 2; len <= n;len++){for (int l = 1; l + len - 1 <= n;l++){int r = l + len - 1;if(len==2){cost[l][r] = !(s[l] == s[r]);continue;}cost[l][r] = cost[l + 1][r - 1] + !(s[l] == s[r]);}}memset(dp, 0x3f, sizeof dp);dp[0][0] = 0;for (int i = 1; i <= n;i++){for (int j = 1; j <= K;j++){for (int k = 0; k < i;k++){dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost[k + 1][i]);}}}int ans = 1e9;int num = n;for (int i = 1; i <= K;i++){if(dp[n][i]<ans){ans = dp[n][i];num = i;}}cout << ans << endl;Print(n, num);
}
Problem - 577B - Codeforces
注意：这里不是连续的子序列
要用鸽巢原理优化 \(n\) 的大小！！！
因为 \(n>m\) 时，一定会得到两个前缀和余数相等（余数是0 ~ m-1）
然后01背包解决即可
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair<int, int>
const LL mod = 998244353;
const int N = 1e6+10;
int a[N];
int dp[1010][1010];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= n;i++){cin >> a[i];a[i] %= m;}if(n>m){cout << "YES\n";return 0;}for (int i = 1; i <= n;i++){dp[i][a[i]] = 1;for (int j = 0; j < m;j++){dp[i][j] |= dp[i - 1][j];dp[i][(j + a[i]) % m] |= dp[i - 1][j];}if(dp[i][0]){cout << "YES\n";return 0;}}cout << "NO\n";
}
bitset优化解法：
[!tip]
1️⃣ bitset 左移行为
对于bitset<N>：bitset<N> b; b << k; // 左移 k 位
- 要求：
0 ≤ k ≤ N- 结果：
- 左移 k 位，高位被丢弃。
- 低位补 0。
- 未定义行为：
k > N（超过 bitset 大小才有问题）。
[!info] 时间复杂度
但bitset大概把它分成：1000 / 64 ≈ 16块来处理。
//对于每个操作时间复杂度为 O(m/64)（较原先 O(m)优化一点点，会快一点） dp << x dp >> (m - x) dp | something dp & mask
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair<int, int>
const LL mod = 998244353;
const int N = 1010;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;if(n>m){cout << "YES\n";return 0;}bitset<N> dp, mask;for (int i = 0; i < m;i++){//限制范围mask[i] = 1;}for (int i = 1; i <= n; i++){int x;cin >> x;x %= m;dp |= ((dp << x) | (dp >> (m - x))) & mask;dp[x] = 1;//注意if(dp[0]){cout << "YES\n";return 0;}}cout << "NO\n";
}
Problem - 1153D - Codeforces
很妙的一道树形dp+贪心，代码不长，挺锻炼思维
思考根节点受几个叶子节点影响，然后找最大可能
另外这里叶子节点要自己判断一下，还有如果是求max的话，dp[u]先初始化为 inf
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair<int, int>
const LL mod = 998244353;
const int N = 3e5+10;
int op[N], dp[N];
vector<int> e[N];
int cnt;void dfs(int u,int fa){bool flag = 0;if(op[u]==1)dp[u] = 1e9;elsedp[u] = 0;for(auto v:e[u]){if(v==fa)continue;dfs(v, u);flag = 1;if(op[u]==1){dp[u] = min(dp[u], dp[v]);}else{dp[u] += dp[v];}}if(flag==0){//是叶子节点cnt++;dp[u] = 1;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> op[i];}for (int i = 2; i <= n;i++){int fa;cin >> fa;e[fa].push_back(i);e[i].push_back(fa);}dfs(1, 0);cout << cnt - dp[1] + 1 << endl;
}