XP04 - day04
2026-08-16 09:17:35
发布于：广东
101阅读
0回复
0点赞
吃奶酪
#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
double x, y;
} a[20];
double get(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double dp[1<<15][15];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++) dp[i][j]=1e9;
}
//初始情况 考虑
// （0，0）-> (x,y)
// 0000 0001 0010 0100 1000
for(int i=0;i<n;i++){
dp[1<<i][i]=get(a[i].x,a[i].y,0,0);
}
//dp[i][j]
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(i>>j&1){//保证状态合法
for(int k=0;k<n;k++){
if((i>>k&1)==0){
double dis=get(a[j].x,a[j].y,a[k].x,a[k].y);
dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dis);
}
}
}
}
}
double ans=1e9;
for(int i=0;i<n;i++){
ans=min(ans,dp[(1<<n)-1][i]);
}
printf("%.2f",ans);
return 0;
}
最小异或值之和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=14;
int n;
ll a[N],b[N],dp[1<<N];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
for(int i=0;i<1<<n;i++)dp[i] = 1e18;
dp[0] = 0;
for(int i=0;i<1<<n;i++){
// i 二进制状态下 他第j位是
int cnt = 0; //二进制数量
for(int j=0;j<n;j++){
if(i>>j&1)cnt++;
}
for(int j=0;j<n;j++){
if((i>>j&1)==0){
dp[i+(1<<j)] = min(dp[i+(1<<j)],dp[i]+(b[j]^a[cnt]));
}
}
}
cout<<dp[(1<<n)-1];
return 0;
}
动态规划与背包专题笔记
一、数字三角形
状态
dp[i][j]：从 (1,1) 出发走到 (i,j) 能得到的最大路径和。
转移
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll a[N][N],dp[N][N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
dp[1][1]=a[1][1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
}
}
ll ans=0;
for(int j=1;j<=n;j++){
ans=max(ans,dp[n][j]);
}
cout<<ans;
return 0;
}
二、01 背包——最大价值
1. 二维 DP
状态
dp[i][j]
表示：
前
i个物品，背包容量不超过j时的最大价值。
对于第 i 个物品：
不选：
dp[i-1][j]
选：
dp[i-1][j-w[i]]+v[i]
所以：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
二维代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N][N];
int w[N],v[N];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
2. 一维优化
观察：
dp[i][j]
只会使用：
dp[i-1][...]
所以第一维可以删掉。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int w,v;
cin>>w>>v;
for(int j=m;j>=w;j--){
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[m];
return 0;
}
为什么倒序？
二维中：
dp[i][j-w]
不能参与转移，必须使用：
dp[i-1][j-w]
所以一维时从大到小更新，保证 dp[j-w] 还是上一层。
01背包：倒序
三、01 背包——方案数
1. 二维 DP
状态
dp[i][j]：
前
i个物品，恰好凑出重量j的方案数。
第 i 个物品：
不选：
dp[i-1][j]
选：
dp[i-1][j-w[i]]
所以：
dp[i][j]=dp[i-1][j];
if(j>=w[i])dp[i][j]+=dp[i-1][j-w[i]];
初始化
dp[0][0]=1;
二维代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N][N];
int w[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]+=dp[i-1][j-w[i]];
}
}
}
cout<<dp[n][m];
return 0;
}
2. 一维优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N];
int n,m;
int main(){
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;i++){
int w;
cin>>w;
for(int j=m;j>=w;j--){
dp[j]+=dp[j-w];
}
}
cout<<dp[m];
return 0;
}
还是倒序：
因为每件物品只能使用一次。
四、完全背包——最大价值
每种物品可以使用无限次。
1. 二维 DP
状态
dp[i][j]：
前
i种物品，容量不超过j时的最大价值。
不选第 i 种：
dp[i-1][j]
选择第 i 种：
dp[i][j-w[i]]+v[i]
注意这里和 01 背包不同：
01背包：
dp[i-1][j-w[i]]
完全背包：
dp[i][j-w[i]]
因为当前物品还能继续选。
转移
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
二维代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N][N];
int w[N],v[N];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
2. 一维优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int w,v;
cin>>w>>v;
for(int j=w;j<=m;j++){
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[m];
return 0;
}
为什么正序？
因为二维转移本来就是：
dp[i][j-w[i]]
也就是允许使用当前这一层刚刚算出的状态。
所以：
01背包：倒序
完全背包：正序
五、装箱问题
本质：
剩余空间最小
=
装入总体积最大
每件物品只能使用一次，所以是 01 背包。
1. 二维 DP
状态
dp[i][j]：
前
i个物品，容量不超过j时最多能够装入多少体积。
转移
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+w[i]);
}
二维代码
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int dp[N][20010];
int w[N];
int V,n;
int main(){
cin>>V;
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=V;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]){
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+w[i]);
}
}
}
cout<<V-dp[n][V];
return 0;
}
存在性01背包
// 01背包 存在性问题
//dp[i][j] 考虑完前i个物品此时是否恰好可以装下j的体积
#include<bits/stdc++.h>
using namespace std;
int n,V;
int v[31];
bool dp[31][20010];//考虑完前i个物品此时是否恰可以装下j的体积
int main(){
cin>>V;
cin>>n;
for(int i=1;i<=n;i++)cin>>v[i];
dp[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=V;j++){
dp[i][j] |= dp[i-1][j];
if(j-v[i]>=0)dp[i][j] |= dp[i-1][j-v[i]];
}
}
for(int j=V;j>=0;j--){
if(dp[n][j]){
cout<<V-j;
break;
}
}
return 0;
}
2. 一维优化
#include<bits/stdc++.h>
using namespace std;
const int N=20010;
int dp[N];
int V,n;
int main(){
cin>>V;
cin>>n;
for(int i=1;i<=n;i++){
int w;
cin>>w;
for(int j=V;j>=w;j--){
dp[j]=max(dp[j],dp[j-w]+w);
}
}
cout<<V-dp[V];
return 0;
}
六、摆花——有限数量方案数
第 i 种花最多放 a[i] 盆。
1. 二维 DP
状态
dp[i][j]：
前
i种花，一共摆j盆的方案数。
第 i 种花可以摆：
0
1
2
...
a[i]
所以：
dp[i][j]
=
dp[i-1][j]
+dp[i-1][j-1]
+...
+dp[i-1][j-a[i]]
二维代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int mod=1e6+7;
int a[N];
int dp[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=a[i]&&k<=j;k++){
dp[i][j]+=dp[i-1][j-k];
dp[i][j]%=mod;
}
}
}
cout<<dp[n][m];
return 0;
}
2. 一维优化
这里也可以压成一维。
因为当前第 i 种花最多只能使用 a[i] 次，所以容量要倒序。
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int mod=1e6+7;
int dp[N];
int a[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=1;k<=a[i]&&k<=j;k++){
dp[j]=(dp[j]+dp[j-k])%mod;
}
}
}
cout<<dp[m];
return 0;
}
这里：
原来的 dp[j]
对应第 i 种花放 0 盆。
然后：
dp[j-k]
对应第 i 种花摆 k 盆。
七、多重背包
每种物品：
重量 w[i]
价值 v[i]
数量 c[i]
1. 二维 DP
状态
dp[i][j]：
前
i种物品，容量不超过j时能够获得的最大价值。
第 i 种物品可以选：
0 ~ c[i] 个
所以：
dp[i][j]
=
max(
dp[i-1][j],
dp[i-1][j-w]+v,
dp[i-1][j-2w]+2v,
...
)
二维代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
const int M=20010;
ll dp[N][M];
int w[N],v[N],c[N];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i]>>c[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
for(int k=1;k<=c[i]&&k*w[i]<=j;k++){
dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+1LL*k*v[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
2. 一维优化
删掉第一维以后：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20010;
ll dp[N];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int w,v,c;
cin>>w>>v>>c;
for(int j=m;j>=0;j--){
for(int k=1;k<=c&&k*w<=j;k++){
dp[j]=max(dp[j],dp[j-k*w]+1LL*k*v);
}
}
}
cout<<dp[m];
return 0;
}
1. A7934 最长上升子序列
状态：
dp[i] = 以 a[i] 结尾的最长上升子序列长度
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],dp[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
复杂度：
O(n^2)
3. A20908 石子合并
典型 区间 DP。
状态：
dp[l][r]
=
把第 l 堆到第 r 堆合并成一堆的最小代价
枚举最后一次在哪里分开：
[l,k] + [k+1,r]
转移：
dp[l][r]
=
min(dp[l][r],
dp[l][k]+dp[k+1][r]+sum(l,r))
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=310;
const ll INF=1e18;
ll a[N],s[N];
ll dp[N][N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
dp[l][r]=INF;
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],
dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
}
}
}
cout<<dp[1][n];
return 0;
}
复杂度：
O(n^3)
4. U48931 打家劫舍
相邻房屋不能同时选择。
状态：
dp[i]
=
前 i 间房屋能偷到的最大金额
第 i 间房：
不偷：
dp[i-1]
偷：
dp[i-2]+a[i]
所以：
dp[i]=max(dp[i-1],dp[i-2]+a[i]);
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N],dp[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[1]=a[1];
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-1],dp[i-2]+a[i]);
}
cout<<dp[n];
return 0;
}
1. T112030 双重限制藏宝计划
这是 二维费用 01 背包：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll dp[N][N];
int n,V,M;
int main(){
cin>>n>>V>>M;
for(int i=1;i<=n;i++){
int v,m,w;
cin>>v>>m>>w;
for(int j=V;j>=v;j--){
for(int k=M;k>=m;k--){
dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);
}
}
}
cout<<dp[V][M];
return 0;
}
核心：
dp[j][k]
表示：
体积不超过
j、重量不超过k时的最大价值。
因为每件宝藏只能选一次，所以两个容量都要倒序：
for(int j=V;j>=v;j--)
for(int k=M;k>=m;k--)
2. T112033 哥布林的秘宝密码
这是标准 最长公共子序列 LCS。
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int dp[N][N];
string a,b;
int main(){
cin>>a>>b;
a=" "+a;
b=" "+b;
int n=a.size()-1;
int m=b.size()-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[n][m];
return 0;
}
状态：
dp[i][j]
表示：
字符串
a前i个字符和字符串b前j个字符的最长公共子序列长度。
如果：
a[i]==b[j]
说明两个字符可以同时接上：
dp[i][j]=dp[i-1][j-1]+1;
否则只能舍弃其中一个：
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
二进制枚举
#include<bits/stdc++.h>
using namespace std;
int n, a[15];
int ans;
bool isPrime(int x) {
if(x < 2) return 0;
for(int i = 2; i <= sqrt(x); i ++) {
if(x % i == 0) return 0;
}
return 1;
}
int main() {
cin >> n;
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
// 二进制枚举
// 3
// 000
// 001
// 010
// 011
// 100
// 101
// 110
// 111 状态压缩
// 二进制枚举
int ans = 0;
for(int i=0;i<1<<n;i++){
//枚举状态每一个是不是1
int sum = 0;
for(int j=0;j<n;j++){
if(i>>j&1){
sum+=a[j];
}
}
if(isPrime(sum))ans++;
}
cout<<ans;
return 0;
}
状压 DP：最小异或值之和
1. 核心问题
每个 a[i] 要匹配一个不同的 b[j]，目标是：
(a[0]^b[?]) + (a[1]^b[?]) + ...
最小。
本质就是：
每次给当前
a[i]选一个还没用过的b[j]。
2. 状态表示
dp[s]
表示：
已经使用了状态
s中这些b后，最小异或和。
例如：
s = 0101
表示：
b[0] 用过
b[1] 没用
b[2] 用过
b[3] 没用
3. 当前处理哪个 a
int cnt=__builtin_popcount(s);
cnt 就是已经用了多少个 b。
因此前面已经匹配了：
a[0] ~ a[cnt-1]
当前处理：
a[cnt]
4. 枚举一个没用过的 b
判断：
if((s>>j&1)==0)
说明 b[j] 还没使用。
把它加入：
int ns=s|(1<<j);
转移：
dp[ns]=min(dp[ns],dp[s]+(a[cnt]^b[j]));
5. 初始化和答案
dp[0]=0;
表示一个 b 都没选，代价为 0。
其他状态：
dp[i]=INF;
最终所有 b 都使用：
dp[(1<<n)-1]
就是答案。
6. 核心代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=25;
const int M=(1<<20)+10;
const ll INF=1e18;
int n;
ll a[N],b[N];
ll dp[M];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
for(int i=0;i<1<<n;i++)dp[i]=INF;
dp[0]=0;
for(int s=0;s<1<<n;s++){
int cnt=__builtin_popcount(s);
for(int j=0;j<n;j++){
if((s>>j&1)==0){
int ns=s|(1<<j);
dp[ns]=min(dp[ns],dp[s]+(a[cnt]^b[j]));
}
}
}
cout<<dp[(1<<n)-1];
return 0;
}
7. 一句话理解
s → 哪些 b 已经用过
popcount(s) → 已经用了几个 b
a[cnt] → 当前要匹配的 a
s|(1<<j) → 把 b[j] 标记为已使用
所以状压 DP 本质就是：
用二进制状态记录“哪些东西已经选过”，代替全排列。
复杂度：
状态数：2^n
每个状态枚举 n 个 b
总复杂度：O(n*2^n)
有帮助，赞一个