Frog1
板子题，\(dp[i]\)为跳到\(i\)的花费，每次可能从前两个和前一个跳过来，取最小。
\(dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]))\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=1e5+100;
const ll inf=0x3f3f3f3f;
int t,n,a[max_n],dp[max_n];
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
dp[0]=0;dp[1]=abs(a[0]-a[1]);
for(int i=2;i<n;i++){
dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i-1]-a[i]));
}cout<<dp[n-1]<<endl;
return 0;
}
Frog2
同上，变成了\(k\)步，注意到\(k\)的范围较小，可以直接加上一层循环。
\(dp[i]=min(dp[i],dp[i-k]+abs(a[i-k]-a[i]))\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=1e5+100;
const ll inf=0x3f3f3f3f;
int t,n,a[max_n],dp[max_n],k;
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
dp[0]=0;
for(int i=1;i<n;i++){
dp[i]=inf;
for(int j=1;j<=k;j++){
if(i-j>=0) {
dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
}else break;
}
}cout<<dp[n-1]<<endl;
return 0;
}
Vacation
维护三个数组代表当天做的三种事情，更新时加上对应的快乐值，转移方程见代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=1e5+100;
const ll inf=0x3f3f3f3f;
int t,n,a[max_n][5],dp[max_n][5];
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<3;j++)
cin>>a[i][j];
for(int i=0;i<3;i++){
dp[0][i]=a[0][i];
}
for(int i=1;i<n;i++){
dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
dp[i][2]=max(dp[i-1][1],dp[i-1][0])+a[i][2];
}cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
return 0;
}
Knapsack 1
打板子打板子！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=1e5+100;
const ll inf=0x3f3f3f3f;
ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(cin>>n>>m){
for(int i=0;i<n;i++){
cin>>p[i]>>q[i];
}
memset(dp,0,sizeof(dp));
ll ans=0;
for(int i=0;i<n;i++){
for(int j=m;j>=p[i];j--){
dp[j]=max(dp[j],dp[j-p[i]]+q[i]);
ans=max(ans,dp[j]);
}
}cout<<ans<<endl;
}
return 0;
}
Knapsack 2
很有意思的思路，价值是远小于重量的最大值的，所以把原本的目标改为求一定价值下的最小重量。
初始化的时候要注意的是，\(dp[j]\)应该赋值为\(\infty\),但是\(dp[0]\)应该赋值为0，因为如果你装有0价值的东西，那么你用了的体积应该是0。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=2e5+100;
const ll inf=0x3f3f3f3f;
ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
ll wmax=0,sum=0;
for(int i=0;i<n;i++){
cin>>q[i]>>p[i];
sum+=p[i];
}
memset(dp,0x3f,sizeof(dp));
ll ans=0;
dp[0]=0;
for(int i=0;i<n;i++){
for(ll j=sum;j>=p[i];j--){
dp[j]=min(dp[j],dp[j-p[i]]+q[i]);
if(dp[j]<=m){
ans=max(ans,j);
}
}
}cout<<ans<<endl;
return 0;
}
任务安排1
之前讲过的，贪心+前缀和。\(dp[i]\)表示只做前\(i\)个任务所需最短时间，每次\(j\)从\(0\)到\(i-1\)循环，表示将任务从\(j\)处分割开来，具体的转移方程见代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=2e5+100;
const ll inf=0x3f3f3f3f;
ll n,m,t[max_n],c[max_n],dp[max_n];
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t[i]>>c[i];
t[i]+=t[i-1];
c[i]+=c[i-1];
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=i-1;j++){
ll cost=c[i]*t[i]+m*c[n]-c[j]*(t[i]+m);
dp[i]=min(dp[i],dp[j]+cost);
}
}cout<<dp[n]<<endl;
return 0;
}
LCS
朴素LCS算法是\(O(n^2)\)复杂度，转移方程是：
\(
s[i]==t[i]:dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)
\)
\(
s[i]!=t[i]:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
\)
这个题由于是1-n的全排列，所以可以优化到
\(
O(nlog(n))
\)
显然如果其中一个字符串为1-n，那么答案就是另一个串的LIS，所以
定义一个映射\(f(s)={1,2...,n}\)。这样就只要求出\(f(t)\)的LIS长度即为答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8;
const ll max_n=1e6+1000;
const ll inf=0x3f3f3f3f;
ll n,a[max_n],m,dp[max_n];
map<int,int> fun;
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
fun[m]=i;
}
for(int i=1;i<=n;i++){
cin>>m;
a[i]=fun[m];
}
fill(dp,dp+n+10,inf);
ll res=0;
for(int i=1;i<=n;i++){
*lower_bound(dp+1,dp+1+n,a[i])=a[i];
}
for(int i=1;i<=n;i++){
if(dp[i]==inf){
res=i-1;
break;
}
}
cout<<(res==0?n:res)<<endl;
return 0;
}