神秘集中营第四天全知识点、题解总结
2026-08-05 21:01:47
发布于：浙江
动态规划（dp）:
定义等不再赘述
直接上例题：
1.打家劫舍【模版题】
链接：https://www.acgo.cn/problemset/info/48931?homeworkId=23640&teamCode=2042058713337094144
思路：因为不能抢劫相邻两幢房子，所以dp[i]的值只能从dp[i-2]或dp[i-3]中转移过来
而dp[i-4]若最大，则已被dp[i-2]包括，无需考虑
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
typedef long long ll;
ll n,a[N],dp[N];
int main(){
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
dp[1] = a[1];
dp[2] = a[2];
for(int i = 3;i <= n;i++){
dp[i] = max(dp[i-2],dp[i-3]) + a[i];
}
cout << max(dp[n],dp[n-1]);
return 0;
}
2.气象操控
链接：https://www.acgo.cn/problemset/info/137605?homeworkId=23640&teamCode=2042058713337094144
思路：只有前一天是雨天、后一天是晴天，愉悦值才能增加
所以要考虑每天的总获得cost，计算公式：if(k == 0 && j == 1) cost += y[i-1];
if(s[i] == 'R' && j == 1 || s[i] == 'S' && j == 0) cost -= x[i];
最后，dp[i][j]就是自己（不操控气象）和dp[i-1][k] + cost（操控气象）中的最大值
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T;
void solve(){
ll n;
string s;
cin >> n >> s;
s = " " + s;
vector<ll> x(n+1);
vector<ll> y(n+1);
for(int i = 1;i <= n;i++){
cin >> x[i];
}
for(int i = 1;i < n;i++){
cin >> y[i];
}
vector<vector<ll>> dp(n+1,vector<ll>(2,-1e18));
ll Max = 0;
dp[0][0] = 0;
for(int i = 1;i <= n;i++){
for(int j = 0;j < 2;j++){
for(int k = 0;k < 2;k++){
ll cost = 0;
if(k == 0 && j == 1) cost += y[i-1];
if(s[i] == 'R' && j == 1 || s[i] == 'S' && j == 0) cost -= x[i];
dp[i][j] = max(dp[i][j],dp[i-1][k] + cost);
}
Max = max(Max,dp[i][j]);
}
}
cout << Max << "\n";
}
int main(){
cin >> T;
while(T--) solve();
return 0;
}
3.[CSP-J 2022] 上升点列
CSP-J真题！！！
链接：https://www.acgo.cn/problemset/info/696?homeworkId=23640&teamCode=2042058713337094144
思路：先考虑特殊情况，即k为0，只需要求出已给出点列中最长的上升部分即可，与LIS类似
当考虑完特殊情况后，再考虑加上k个点的一般情况：
对于当前的n个点排序按照x然后y，从小到大
f[i][j]以当前第i个点作为结尾，还剩下j个自由点
max(f[i][j]+j);
当前的这个点为最后一个，还剩下j个直接拼接后面
枚举合法状态下的第k个点(坐标不超过i),假设d为距离
中间使用d-1个自由点
f[i][j]=max(f[k][j+d-1]+d);
三层for循环：第一层枚举结尾点是第几个点，第二层枚举剩下数量，第三层枚举结尾点前面的一个点计算转移
最后，若还剩下一个或多个点没有被使用，就可以直接拼在结尾后面，即直接将答案加上剩余数量
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
typedef long long ll;
ll n,k;
struct node{
ll x,y;
}a[N];
bool cmp(node a,node b){
if(a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
ll dp[N][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i].x >> a[i].y;
}
ll Max = -1;
sort(a+1,a+n+1,cmp);
for(int i = 1;i <= n;i++){
dp[i][0] = 1;
for(int j = 0;j <= k;j++){
for(int z = 1;z < i;z++){
if(a[z].x <= a[i].x && a[z].y <= a[i].y){
ll dis = a[i].x - a[z].x + a[i].y - a[z].y;
if(j - dis + 1 >= 0){
dp[i][j] = max(dp[i][j],dp[z][j - dis + 1] + dis);
}
}
}
}
}
for(int i = 1;i <= n;i++){
for(int j = 0;j <= k;j++){
Max = max(Max,dp[i][j] + k - j);
}
}
cout << Max;
return 0;
}
4.吃奶酪
链接：https://www.acgo.cn/problemset/info/90643?homeworkId=23640&teamCode=2042058713337094144
这题需要使用状态压缩（状压）dp
思路：将每块奶酪的选（1）或不选（0）变成一个序列（如1010），此时发现其正好对应二进制的所有数，所以可以将此序列转为一个二进制数，再转为十进制，就可以只用一维来表示选择情况
dp[i][j]:最后选了第i块奶酪，选择的奶酪是[j]的二进制中为1的数位
状态转移方程式：dp[j][mask + (1 << j)] = min(dp[j][mask + (1 << j)],dp[i][mask] + dis(i,j))
最后，因为1111表示全选，所以最后在答案中要比较出所有dp[i][(1 << n) - 1]中的最大值。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 18;
typedef long long ll;
typedef double db;
db x[N],y[N];
db dp[N][1<<N];
const db INF = 1e18;
db dis(int i,int j){
db ddd = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
return ddd;
}
void solve(){
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> x[i] >> y[i];
for(int i = 0;i < n;i++){
for(int j = 0;j < 1 << n;j++){
dp[i][j] = INF;
}
}
for(int i = 0;i < n;i++){
dp[i][1<<i] = dis(i,n+1);
}
for(int mask = 0;mask < 1 << n;mask++){
for(int i = 0;i < n;i++){
if(!(mask >> i & 1)) continue;
for(int j = 0;j < n;j++){
if(!(mask >> j & 1)){
dp[j][mask + (1 << j)] = min(dp[j][mask + (1 << j)],dp[i][mask] + dis(i,j));
}
}
}
}
double Min = INF;
for(int i = 0;i < n;i++) Min = min(Min,dp[i][(1 << n) - 1]);
printf("%.2lf",Min);
}
int main(){
solve();
return 0;
}
全部评论 3
你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压你咋会状压我不会状压
1周前 来自 广东
0
有帮助，赞一个