DP
早上也是成功的没讲课，所以我们要打题（悲 :laughing:
不知道为什么博客到后面全部都斜体了
1.合唱队形
2501 OJ：P264
思路：先从前面扫一遍，用dp1记录最长上升子序列
再从后面扫一遍，用dp2记录最长上升子序列
然后sum=dp1[i]+dp2[i]-1;
枚举i（中间点），取sum 的最大值
代码如下：
#include
using namespace std;
int n,a[1100],dp1[1100],dp2[1100];
int main()
{
cin>>n;
for(int i=1;i>a[i],dp1[i]=1,dp2[i]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]=1;i--)
for(int j=n;j>i;j--)
if(a[j]<a[i]) dp2[i]=max(dp2[i],dp2[j]+1);
int sum=0,maxn=-1;
for(int i=1;i<=n;i++)
{
sum=dp1[i]+dp2[i]-1;
maxn=max(maxn,sum);
}
cout<<n-maxn;
return 0;
}
2.低价购买（洛谷：P1108）
第一问：就是最长下降子序列
第二问：很神奇的在dp数组上的dp
f[i]表示以第i个 数字结尾的最长子序列的个数
简单来说：
- 如果dp[i]=1 f[i]=1;
- j:1 i-1 判断如果a[j]>a[i] 并且dp[i]=dp[j]+1,说明i可以从j转来，f[i]+=f[j]
- a[i]=a[j] && dp[i]=dp[j] 说明重复了，直接赋值为0
代码如下：
#include
using namespace std;
int n,a[5100],dp[5100],f[5100];
int main()
{
cin>>n;
for(int i=1;i>a[i],dp[i]=1;
for(int i=1;i<=n;i++)
for(int j=1;ja[i]) dp[i]=max(dp[i],dp[j]+1);
int sum=-1;
for(int i=1;i<=n;i++) sum=max(sum,dp[i]);
cout<<sum<<" ";
int sum2=0;
for(int i=1;i<=n;i++)
{
if(dp[i]==1) f[i]=1;
for(int j=1;ja[i] && dp[i]==dp[j]+1) f[i]+=f[j];
else if(a[j]==a[i] && dp[i]==dp[j]) f[i]=0;
}
}
for(int i=1;i<=n;i++)
if(dp[i]==sum) sum2+=f[i];
cout<<sum2;
return 0;
}
3.零件分组（2501 OJ：P1441）
和拦截导弹第二问十分的相似
先排序一下（按长度）
开一个数组f，f[i]表示第i个分组最后的元素
分组时，找到与i 的重量最近的，但是f[c]<=i
如果没有，就增加一个分组
代码如下：
#include
using namespace std;
int n,f[1100];
struct node
{
int l;//长度
int w;//重量
}a[1100];
bool cmp(node x,node y)
{
if(x.l==y.l) return x.w>y.w;
return x.l>y.l;
}
int main()
{
// freopen("stick.in","r",stdin);
// freopen("stick.out","w",stdout);
cin>>n;
for(int i=1;i>a[i].l>>a[i].w;
sort(a+1,a+n+1,cmp);
int c=1;
f[1]=a[1].w;
for(int i=1;i<=n;i++)
{
int fi=0;
//sort(f+1,f+c+1);
for(int j=1;j=a[i].w)
{
fi=1;
f[j]=a[i].w;
a[i].w=0x3f3f3f3f;
}
}
// cout<<fi<<endl;
if(fi==0)
{
c++;
f[c]=a[i].w;
}
}
cout<<c;
return 0;
}
a.最大利润
题目：
思路：
a[i]记录到i的最大利润
判断选和不选i有什么不同
然后取max
#include
using namespace std;
int m,a[100005];
int main()
{
cin>>m;
int maxn=-0x3f3f3f3f;
for(int i=1;i>a[i];
a[i]=max(a[i],a[i]+a[i-1]);
maxn=max(maxn,a[i]);
}
cout<<maxn;
return 0;
}
b.排队吃饭
- 思路：
先求最长不下降序列和最长上升子序列
判断哪个更大，答案为n-大的那一个 - 代码：
#include
using namespace std;
int n,a[30100],dp1[31100],dp2[31100],maxn1,maxn2;
int main()
{
cin>>n;
for(int i=1;i>a[i],dp1[i]=1,dp2[i]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
if(a[j]<=a[i]) dp1[i]=max(dp1[i],dp1[j]+1);
maxn1=max(maxn1,dp1[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j=a[i]) dp2[i]=max(dp2[i],dp2[j]+1);
maxn2=max(maxn2,dp2[i]);
}
cout<<n-max(maxn1,maxn2);
return 0;
}
c.方格取数（2501 OJ P3966）
很神奇的CE了特别多次
后来才发现我有2个方格取数，不知道为什么电脑把我改的程序另存为了，还没改名字
然后就提交错了，真离谱 :sweat_smile:
上下右，翻转90度后就是左右下
f[i][j][0/1]到达（i，j）了，0表示左，1表示右
向下走
f[i][j][0]=max(f[i][j][0],max(f[i-1][j][0],f[i-1][j][1])+a[i][j]);
f[i][j][1]=max(f[i][j][1],max(f[i-1][j][0],f[i-1][j][1])+a[i][j]);
向左走就是
f[i][j][0]=max(f[i][j][0],f[i][j−1][0]+a[i][j])
向右走就是
f[i][j][1]=max(f[i][j][1],f[i][j+1][1]+a[i][j])
两个方向一个要正序，一个倒序
#include
#define int long long
using namespace std;
int n,m,a[1005][1005],f[1005][1005][2];
signed main()
{
cin>>n>>m;
for(int i=1;ia[j][i];
swap(n,m);//翻转90度
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
{
f[i][j][1]=(int)(-1e18);
f[i][j][0]=(int)(-1e18);
}
f[1][1][0]=f[1][1][1]=a[1][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j=1;j--)
if(j!=m) f[i][j][1]=max(f[i][j][1],f[i][j+1][1]+a[i][j]);
}
cout<<max(f[n][m][1],f[n][m][0]);
return 0;
}
d.买干草
题目：
完全背包问题，无限多包，很明显是一道完全背包模板题
但是要注意：是至少，所以要枚举 j 到h+5000，
并且是最少的钱，取最小值，要把max改成min
#include<bits/stdc++.h>
using namespace std;
int n,h,c[110],w[110],f[55005];
int main()
{
cin>>n>>h;
memset(f,0x3f3f3f3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
{
for(int j=w[i];j<=h+5000;j++)
{
f[j]=min(f[j],f[j-w[i]]+c[i]);
}
}
int minn=f[h];
for(int j=h+1;j<=h+5000;j++) minn=min(minn,f[j]);
cout<<minn;
return 0;
}
```
#### e.金明的预算方案
一个很傻逼的01背包
v[i][j]，p[i][j]表示第i 个主件的第j 个附件的价格和重要度
（j=0时，i是主件）
分为以下五种情况
- 什么都不买
- 只买主件
- 买主件和第一个附件
- 买主件和第二个附件
- 买主件和两个附件
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,vi,qi,pi;
int v[65][3],p[65][3],f[32005];//第i个物品的第j个附件的价格和重要度
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>vi>>pi>>qi;//价格，重要度，主件
if(qi==0)
{
v[i][0]=vi;
p[i][0]=pi;
}
else
{
if(v[qi][1]==0)
{
v[qi][1]=vi;
p[qi][1]=pi;
}
else
{
v[qi][2]=vi;
p[qi][2]=pi;
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=n;j>=0;j--)
{
if(j>=v[i][0]) f[j]=max(f[j],f[j-v[i][0]]+v[i][0]*p[i][0]);
if(j>=(v[i][0]+v[i][1])) f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]);
if(j>=(v[i][0]+v[i][2])) f[j]=max(f[j],f[j-v[i][0]-v[i][2]]+v[i][0]*p[i][0]+v[i][2]*p[i][2]);
if(j>=(v[i][0]+v[i][1]+v[i][2])) f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]+v[i][2]*p[i][2]);
}
}
cout<<f[n];
return 0;
}