算法复习（四、五、六）

动态规划

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构、重叠子问题

关于动态规划算法和备忘录方法的适用条件：

要求：
用分治法和动态规划法分别解决最大子段和问题（第四步求最优解不需要掌握）

掌握用动态规划法解决0-1背包问题

最长单调递增子序列

最长公共子序列（会写出计算最长公共子序列长度的递推式即可）

矩阵连乘问题

备忘录做法：

signed main()
{cin>>n;for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;for(int i=1;i<=n;i++) dp[i][i]=0;for(int i=1;i<=n;i++)cin>>row[i]>>col[i];for(int i=1;i<=n;i++) p[i]=col[i];p[0]=row[1];for(int len=2;len<=n;len++){for(int i=1;i<=n-len+1;i++){int j=i+len-1;dp[i][j]=dp[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){int tmp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];if(tmp<dp[i][j]){dp[i][j]=tmp;s[i][j]=k;}}}}cout<<dp[1][n]<<endl;dfs(1,n);return 0;
}

动态规划做法：

signed main()
{cin>>n;for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;for(int i=1;i<=n;i++) dp[i][i]=0;for(int i=1;i<=n;i++)cin>>row[i]>>col[i];for(int i=1;i<=n;i++) p[i]=col[i];p[0]=row[1];for(int len=2;len<=n;len++){for(int i=1;i<=n-len+1;i++){int j=i+len-1;dp[i][j]=dp[i][i]+dp[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){if(dp[i][j]>dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]){dp[i][j]=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];s[i][j]=k;}}}}cout<<dp[1][n]<<endl;print(1,n);return 0;
}

最大子段和问题

法一：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n,a[N],dp[N];signed 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]=max(dp[i-1]+a[i],0ll);ans=max(ans,dp[i]);}cout<<ans<<endl;return 0;
}
/*
7
-2 11 -4 13 -5 -2 -100
*/

法二：

signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=0,b=0;for(int i=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];ans=max(ans,b);}cout<<ans<<endl;return 0;
}

法三：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n,a[N],dp[N];
int dfs(int l,int r)
{if(l==r)return a[l]>0?a[l]:0;int sum=0,mid=(l+r)/2;int left=dfs(l,mid);int right=dfs(mid+1,r);int s1=0,s2=0,tmp=0;for(int i=mid;i>=l;i--){tmp+=a[i];if(s1<tmp) s1=tmp;}tmp=0;for(int i=mid+1;i<=r;i++){tmp+=a[i];if(s2<tmp) s2=tmp;}sum=s1+s2;if(left>sum) sum=left;if(right>sum) sum=right;return sum;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cout<<dfs(1,n)<<endl;return 0;
}
/*
7
-2 11 -4 13 -5 -2 100
*/

01背包问题

int n,m,f[105][N],dp[N];void fun1()
{for(int i=1;i<=n;i++)   //物品i{for(int j=1;j<=m;j++)   //容量j{if(j<w[i])f[i][j]=f[i-1][j];else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);}}cout<<f[n][m]<<endl;
}
void fun2() //逆序更新
{for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);}
}

最长单调递增子序列

for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[j]<=a[i])dp[i]=max(dp[i],dp[j]+1);}}cout<<dp[n]<<endl;

最长公共子序列

{cin>>s1>>s2;len1=s1.length(),len2=s2.length();s1=" "+s1,s2=" "+s2;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1,s[i][j]=1;else{if(dp[i-1][j]>dp[i][j-1]){dp[i][j]=dp[i-1][j];s[i][j]=2;//上面}elsedp[i][j]=dp[i][j-1];s[i][j]=3;}}}cout<<dp[len1][len2]<<endl;return 0;
}

贪心算法

适合于贪心算法求解的问题具有：贪心选择性质、最优子结构性质
贪心算法可以获取到问题的局部最优解，不一定能获取到全局最优解
掌握使用贪心算法解决：活动安排问题、背包问题、最优装载问题（件数最多）、删数问题

活动安排问题

按照结束时间进行排序

int n,p[N];
struct node
{int st,ed,id;
}a[N];
bool cmp(node a,node b)
{return a.ed<b.ed;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) {cin>>a[i].st>>a[i].ed;a[i].id=i;}sort(a+1,a+n+1,cmp);p[1]=1;int ans=1,tmp=a[1].ed;for(int i=2;i<=n;i++){if(a[i].st>=tmp){tmp=a[i].ed;ans++;p[i]=1;}}cout<<ans<<endl;return 0;
}

背包问题

int n,p[N];
struct node
{int w,v;double d;
}a[N];
bool cmp(node a,node b)
{return a.d>b.d;
}
signed main()
{cin>>n>>c;for(int i=1;i<=n;i++){cin>>a[i].w>>a[i].v;a[i].d=a[i].v/a[i].w;}sort(a+1,a+n+1,cmp);int i=1;double ans=0;while(i<=n&&a[i].w<=c){c-=a[i].w;ans+=a[i].v;i++;}if(i<=n) ans+=c*a[i].d;cout<<ans<<endl;return 0;
}

最优装载问题（件数最多）

重量轻的先装，找找重量从小到大进行排序

删数问题

找到最近下降点

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N = 7e6+100;
const int mod = 998244353;
int n,k;
string s;signed main()
{cin>>s>>k;n=s.length();if(k>=n)cout<<0<<endl;else{while(k){int i;for(i=0;i<s.length()&&s[i]<=s[i+1];i++);s.erase(i,1);k--;}while(s.size()>1&&s[0]=='0')s.erase(0,1);cout<<s<<endl;}return 0;
}
/**/

第六章

子集树实现素数环

const int N =1e6+5;
int n,a[N],vis[N],ans;
int check(int a,int b)
{int sum=a+b;for(int i=2;i*i<=sum;i++)if(sum%2==0)return 0;return 1;
}
void dfs(int x)
{if(x==n+1){if(check(a[1],a[n]))ans++;return;}for(int i=1;i<=n;i++){if(!vis[i]&&check(a[x-1],i)){vis[i]=1;a[x]=i;dfs(x+1);vis[i]=0;}}
}
void solve()
{cin>>n;dfs(1);cout<<ans<<endl;
}
signed main()
{solve();return 0;
}

排列树实现素数环

int n,a[N],vis[N],ans;
int check(int a,int b)
{int sum=a+b;for(int i=2;i*i<=sum;i++)if(sum%2==0)return 0;return 1;
}
void dfs(int x)
{if(x==n+1){if(check(a[1],a[n]))ans++;return;}for(int i=x;i<=n;i++){swap(a[x],a[i]);if(check(a[x-1],a[x]))dfs(x+1);swap(a[x],a[i]);}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) a[i]=i;dfs(1);cout<<ans<<endl;
}

装载问题

#include <bits/stdc++.h>
#define endl '\n'
#define int long longusing namespace std;
const int N =1e6+5;
const int inf=1e18;
int n,c,a[N],b[N],ans[N],sum,bestcw;
void dfs(int x,int cw)
{if(x==n+1){if(cw>bestcw){for(int i=1;i<=n;i++)ans[i]=b[i];bestcw=cw;}return;}sum-=a[x];if(cw+a[x]<=c){b[x]=1;cw+=a[x];dfs(x+1,cw);cw-=a[x];}if(cw+sum>bestcw){b[x]=0;dfs(x+1,cw);}sum+=a[x];
}
void solve()
{cin>>n>>c;for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];dfs(1,0);cout<<bestcw<<endl;for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
}
signed main()
{solve();return 0;
}

01背包问题（回溯+贪心）

剪枝规则：
约束函数：当选取一个物品时，累计的中部不可大于背包容量C
限界函数：根据物品单位重量的价值进行降序排列，越靠近树根位置剪掉分枝越多从而加快搜索；bound(i)定义为当前选取物品价值的和加上剩余物品的价值和，根据贪心的性质，剩余物品不会比贪心选取的物品方案更优，若bound(i)<=此时最优价值，则进行剪枝。

int n,c,cw,cv,bestv;
struct node
{int w,v;double d;
}a[N];
bool cmp(node a,node b)
{return a.d>b.d;
}
int check(int x)
{int v=cv;int tmp=c-cw;while(x<=n&&a[x].w<=tmp){tmp-=a[x].w;v+=a[x].v;x++;}if(x<=n)v+=1.0*tmp*a[x].w;return v;
}
void dfs(int x)
{if(x==n+1){bestv=cv;return;}if(cw+a[x].w<=c){cw+=a[x].w;cv+=a[x].v;dfs(x+1);cw-=a[x].w;cv-=a[x].v;}if(check(x+1)>bestv)dfs(x+1);
}
signed main()
{cin>>c>>n;for(int i=1;i<=n;i++){cin>>a[i].w>>a[i].v;a[i].d=a[i].v*1.0/a[i].w;}sort(a+1,a+n+1,cmp);dfs(1);cout<<bestv<<endl;return 0;
}
/*
50 3
10 60
30 120
20 100
*/

n皇后问题

int n,m,a[105][105],p[N],ans;
int check(int x)
{for(int i=1;i<x;i++)if(abs(x-i)==abs(p[x]-p[i])||(p[i]==p[x]))return 0;return 1;
}
void dfs(int x)
{if(x==n+1){ans++;for(int i=1;i<=n;i++)cout<<p[i]<<" ";cout<<endl;return;}for(int i=1;i<=n;i++){p[x]=i;if(check(x))dfs(x+1);}
}
signed main()
{cin>>n;dfs(1);if(ans)cout<<ans<<endl;elsecout<<"No Solution!"<<endl;return 0;
}