当前位置：首页 > news >正文

wordpress 迁站/网络推广是网络营销的基础

news 2025/7/2 14:32:44

wordpress 迁站,网络推广是网络营销的基础,开拼多多网店怎么运营,wordpress如何重置后台密码前记： 以前完全没有系统性的学习过DP，只是零零星星的接触过，写过一些题，虽然现在距离结束已经不远了，但是我还是决定回来系统的学一下DP，此篇用于记录我学习DP的题录。参考： 动态规划DP&#…

前记： 以前完全没有系统性的学习过DP，只是零零星星的接触过，写过一些题，虽然现在距离结束已经不远了，但是我还是决定回来系统的学一下DP，此篇用于记录我学习DP的题录。

参考：
动态规划DP：10min从入门到精通
状压DP学习总结

一、我们需要从以下带时间窗的任务中，选择总价值最大的，每次只能做一个任务，而且任务之间的时间不能冲突。每一个矩形上面标的数字代表该任务完成的value。如下所示：
在这里插入图片描述
输入：

输出：

思路：
pre[i]表示第i个任务前的最近任务
dp[i]表示前i个任务的最大利益
则状态转移方程为：

dp[i]=max(dp[i-1],a[i-1].val+dp[pre[i-1]]);

1、不选第i个任务，则最大利益为dp[i-1]
2、选第i个任务，则最大利益为a[i-1]（第i个任务的利益）+dp[pre-1]
dp[i]取两者中的大值

代码：

#pragma GCC optimize(3)
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <bits/stdc++.h>#define ull unsigned long long
#define ll long long
#define inf 2100000000
#define endl '\n'
#define pii pair<int,int>
#define pll pair<long long,long long>
#define MP make_pair
#define eps 1e-6const double pi=3.14159265358;
const int maxn=1e5+10;
const int mod=1e9+7;using namespace std;int dp[maxn];
int pre[maxn];struct node {int st,ed,val;
}a[maxn];bool cmp(node x,node y) {return x.ed<y.ed;
}int main() {ios::sync_with_stdio(false);//cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=0;i<n;i++) {node x;cin>>x.st>>x.ed>>x.val;a[i]=x;}sort(a,a+n,cmp);for(int i=n-1;i>0;i--) {for(int j=i-1;j>=0;j--) {if(a[i].st>=a[j].ed) {pre[i]=j+1;break;}}}dp[0]=0;dp[1]=a[0].val;dp[2]=max(a[0].val,a[1].val);for(int i=2;i<=n;i++) {dp[i]=max(dp[i-1],a[i-1].val+dp[pre[i-1]]);}cout<<dp[n]<<endl;return 0;
}

二、在数组arr=[1,2,4,1,7,8,3]中选出一堆不相邻的数，使之选出的数字之和最大。例如选择数字2,1,8,他们之间就互不相邻，我们想找出最大的数字组合。

输入：

1 2 4 1 7 8 3

输出：

思路：
dp[i]表示前i个数字的利益最大值
则状态转移方程可得：

dp[i]=max(dp[i-1],dp[i-2]+a[i]);

1.不取第i个数字，则取dp[i-1]
2.取第i个数字，则取dp[i-2]+a[i]
dp[i]取其中的大值

代码：

#pragma GCC optimize(3)
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <bits/stdc++.h>#define ull unsigned long long
#define ll long long
#define inf 2100000000
#define endl '\n'
#define pii pair<int,int>
#define pll pair<long long,long long>
#define MP make_pair
#define eps 1e-6const double pi=3.14159265358;
const int maxn=1e5+10;
const int mod=1e4+7;using namespace std;int dp[maxn];
int pre[maxn];
int a[maxn];int main() {ios::sync_with_stdio(false);//cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=0;i<n;i++) {cin>>a[i];}//前两项无法通过递推式获得，先赋初值dp[0]=a[0],dp[1]=a[1];for(int i=2;i<n;i++) {dp[i]=max(dp[i-1],dp[i-2]+a[i]);}for(int i=0;i<n;i++) {cout<<dp[i]<<" ";}cout<<endl;return 0;
}

三、给定一个数组arr=[3,34,4,12,5,2]和整数S=[10,14]，能否在数组arr=中选取一堆数字，使得这些数字之和等于给定整数，如果存在，返回True；否则返回False。
当没法取得和为S的集合时输出0，当可以取得和为S的集合时输出1，并且换行递增输出这些数字

输入：

6
3 34 4 12 5 2

输出：

思路：
（其实我感觉这个思路是dfs，不确定是不是dp，但是原文写了这个方法，那我就当算是dp吧）
dfs(i,s)表示取前i个数字时，能否能组成数字s
则状态转移方程可得：

if(a[now]>s) {dfs(now-1,s);
else {dfs(now-1,s);dfs(now-1,s-a[now]);
}

当第i个数大于s时，考虑前i个数,取dfs(now-1,s);
第i个数小于s时，考虑两种情况：
1.取第i个数，则dfs(now-1,s-a[now]);
2.不取第i个数，则dfs(now-1,s);
递归出口为now==-1或者a[now]==s

代码：

#pragma GCC optimize(3)
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <bits/stdc++.h>#define ull unsigned long long
#define ll long long
#define inf 2100000000
#define endl '\n'
#define pii pair<int,int>
#define pll pair<long long,long long>
#define MP make_pair
#define eps 1e-6const double pi=3.14159265358;
const int maxn=1e5+10;
const int mod=1e4+7;using namespace std;int dp[maxn];
int a[maxn];int flag=0;
vector<vector<int>>ans;
void dfs(int now,int s,vector<int>v) {if(flag) {return;}if(s==0) {flag=1;ans.push_back(v);return;}else if(now==-1) return;else if(a[now]>s) {dfs(now-1,s,v);}else {dfs(now-1,s,v);v.push_back(a[now]);dfs(now-1,s-a[now],v);v.pop_back();}
}int main() {ios::sync_with_stdio(false);//cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=0;i<n;i++) {cin>>a[i];}for(int i=10;i<15;i++) {flag=0;vector<int>v;dfs(n-1,i,v);cout<<flag<<endl;if(flag) {v=ans[0];sort(v.begin(),v.end());for(auto i:v) {cout<<i<<" ";}cout<<endl;ans.pop_back();}}return 0;
}

四、状压入门一题

HDU1565

题意：
给你n*n的矩阵，存不小于0的数，在里面取数，保证取的数两两所在格子不相邻，并且求和最大。

思路：
将每一行的状态写成01串，0表示不取这个格子的数，1表示取这个格子的数。
首先预处理出所有满足要求的01串（保证在此行中取的数不相邻）：即判断数 i 满足(i&(i>>1)==0)。
而判断行与行之间满足要求，只要判断两个串进行与运算为0即可。
f[i][j]表示取前 i 行，第j个状态的值
tot[i]表示第i种满足要求的状态
递推式：

//如果第i行第j种状态与前i-1行第k种状态满足不相邻的要求
//则判断第i行是否取第j种状态（比较与当前值的大小）
if((tot[j]&tot[k])==0) {f[i][j]=max(f[i][j],f[i-1][k]+val);
}

复杂度为O((1<<20)×(1<<20)×n)，这其中还要排除一半以上不满足要求的状态。
代码：

#pragma GCC optimize(3)
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <bits/stdc++.h>#define ull unsigned long long
#define ll long long
#define inf 2100000000
#define endl '\n'
#define pii pair<int,int>
#define pll pair<long long,long long>
#define MP make_pair
#define eps 1e-6const double pi=3.14159265358;
const int maxn=(1<<17);
const int mod=1e9+7;using namespace std;int a[50][50];
int f[21][maxn]; // f[i][j]表示前i行各个状态之和最大值
int tot[maxn]; // 存一行中合法的状态//计算第i行取状态x的值
int calval(int i,int x) {int cnt=1,ans=0;while(x) {if(x&1) ans+=a[i][cnt];x>>=1;cnt++;}return ans;
}int main() {ios::sync_with_stdio(false);//cin.tie(0),cout.tie(0);int n;while(cin>>n) {int cnt=0;//当i&(i>>1)==0时，则状态合法for(int i=0;i<(1<<n);i++) {if((i&(i>>1))==0) {tot[cnt++]=i;}}//dp一般从1开始输入会方便for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {cin>>a[i][j];}}memset(f,0,sizeof(f));for(int i=1;i<=n;i++) {//递推计算前n行for(int j=0;j<cnt;j++) {//暴力cnt种状态的值int val=calval(i,tot[j]);for(int k=0;k<cnt;k++) {if((tot[j]&tot[k])==0) {f[i][j]=max(f[i][j],f[i-1][k]+val);}}}}//所有状态中的最大值int ans=0;for(int i=0;i<cnt;i++) {ans=max(f[n][i],ans);}cout<<ans<<endl;}return 0;
}