Dp专题
YuRuiH_
2018-11-27 17:32:13
# ****P1063 能量项链****
简单的区间dp
通过解决小区间来影响大区间
环形问题 存储的时候存两边 变成 2*N 个元素
code:
```c++
for(int i=1;i<=n;i++)
{
cin>>e[i];
e[i+n]=e[i];
}
```
s[i][j] ------- i到j的最大能量
k ------------ 左右区间划分点
把区间分为2个珠子、3个珠子、4个珠子……
s[i][j]=max(s[i][j],左区间能量+右区间能量+合并后的能量)
合并后=左区间第一个珠子*右区间第一个珠子*总区间最后一个珠子
s[i][j]=max(s[i][j],s[j][k]+s[k+1][i]+e[j]*e[k+!]*e[j])
Code：
```c++
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int e[210];
int s[210][210];
int maxn;
int main()
{
cin.sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>e[i];
e[i+n]=e[i];
}
for(int i=2;i<2*n;i++)
{
for(int j=i-1;i-j<n&&j>=1;j--)
{
for(int k=j;k<i;k++)
{
s[j][i]=max(s[j][i],s[j][k]+s[k+1][i]+e[j]*e[k+1]*e[i+1]);
maxn=max(maxn,s[j][i]);
}
}
}
cout<<maxn;
}
```
------
# **P1133 教主的花园**
三维dp 不好想 但是看了~~题解~~之后明白了
首先 推一下公式
只看当前位置与之前位置的关系
```
1. 如果当前位置种①号树 要且只能满足高矮高 前面可以种②或③号
2. 如果当前位置种②号树 要满足高矮高 前面只能种③号
2. 如果当前位置种②号树 要满足矮高矮 前面只能种①号
3. 如果当前位置种③号树 要且只能满足矮高矮 前面可以种①或②号
```
到这里就差不多了
主要变量：f[i][j][k] 表示第i个位置种第j棵树 k=0 表示递增 k=1 表示递减
转移公式：看代码吧 懒得打了
Code：
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100005
using namespace std;
int a[maxn][5],f[maxn][5][2],n,ans=0;
int main()
{
cin.sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i][1]>>a[i][2]>>a[i][3];
for(int i=2;i<=n;i++)
{
f[i][1][1]=max(f[i-1][2][0],f[i-1][3][0])+a[i][1];
f[i][2][1]=f[i-1][3][0]+a[i][2];
f[i][2][0]=f[i-1][1][1]+a[i][2];
f[i][3][0]=max(f[i-1][2][1],f[i-1][1][1])+a[i][3];
}
ans=max(ans,f[n][1][1]+a[1][2]);
ans=max(ans,f[n][1][1]+a[1][3]);
ans=max(ans,f[n][2][1]+a[1][3]);
ans=max(ans,f[n][2][0]+a[1][1]);
ans=max(ans,f[n][3][0]+a[1][1]);
ans=max(ans,f[n][3][0]+a[1][2]);
cout<<ans;
}
```
------
# **P1095 守望者的逃离**
一道贪心 半dp吧
思路：
```
分两段处理：
①用膜法打败膜法 全部路程都跑膜法
②全部用腿跑 然后用max(用腿，用膜法)
```
思路还是很简单的 就是想不到 唉
代码
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int M,S,T;
int dp[300010];
int main()
{
cin.sync_with_stdio(false);
cin>>M>>S>>T;
for(int i=1;i<=T;i++)
{
if(M>=10)
{
dp[i]=dp[i-1]+60;
M-=10;
}
else
{
dp[i]=dp[i-1];
M+=4;
}
}
for(int i=1;i<=T;i++)
{
dp[i]=max(dp[i],dp[i-1]+17);//核心
if(dp[i]>S)
{
cout<<"Yes"<<endl<<i;
return 0;
}
}
cout<<"No"<<endl<<dp[T];
}
```
------
# **# P1108 低价购买**
```
本题分两块解决
1.求一个最长不下降子序列 </> 等下看代码
2.去重就完事了
3.还有一个技巧 就是边求子序列边处理 我感觉这样会节省时间吧
```
code:
```c++
#include<iostream>
#include<cstdio>
using namespace std;
int a[5010];
int f[5010];
int t[5010];
int now_max;
int now_ans=0;
int now_num;
int main()
{
cin.sync_with_stdio(false);
int N;
cin>>N;
for(int i=1;i<=N;i++)
cin>>a[i];
for(int i=1;i<=N;i++)
{
for(int j=1;j<i;j++)
if(a[i]<a[j])
f[i]=max(f[i],f[j]+1);// 求最长不下降子序列 通用方法
if(f[i]==0)// 如果第i个之前没有不下降子序列 就只有本身有一个
f[i]++;
if(f[i]>now_max)
now_max=f[i];//更新最长的不下降子序列
for(int j=1;j<i;j++)
if(f[i]==f[j]&&a[i]==a[j])
t[j]=0;//判断是否有重复 证明如下：
//如果i的最长不下降子序列的长度=j的最长不下降子序列的长度且满足 他们的结束元素相同 那么一定满足他们属于同一个序列 因此保留一个即可
else
if(f[i]==f[j]+1&&a[i]<a[j])
t[i]+=t[j];// 不然就接在一起
if(!t[i])
t[i]=1;
}
for(int i=1;i<=N;i++)
if(f[i]==now_max)
now_ans+=t[i];// 没什么好说的了
cout<<now_max<<" "<<now_ans;
}
```
#### 做了这么多题 还是找不到dp的思路啊