【必看】DP经典类型题详解-考前刷分技巧

本文主要是介绍【必看】DP经典类型题详解-考前刷分技巧，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点赞关注不迷路！

1.装箱问题

P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

// 洛谷 P1049
// 原题地址 https://www.luogu.com.cn/problem/P1049
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int v;//容积
int n;//物品数
int a[35];
bool b[20005];//打钩数组
int main(){cin>>v>>n;for(int i=1;i<=n;i++){cin>>a[i];}b[0]=1;//必要边界for(int i=1;i<=n;i++){for(int j=v;j>=a[i];j--){if(b[j-a[i]]){b[j]=1;}}}for(int i=v;i>=0;i--){if(b[i]){cout<<(v-i)<<endl;return 0;}}return 0;
}

2.LIS（longest increasing sequence）最长上升子序列

B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

// 洛谷 B3637
// 原题地址：https://www.luogu.com.cn/problem/B3637
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
int a[5005];
int f[5005];
int main(){cin>>n;for(int i=1;i<=n;i++){f[i]=1;cin>>a[i];}for(int i=2;i<=n;i++){int maxv=0;for(int j=1;j<i;j++){if(a[i]>a[j]&&f[j]>maxv){maxv=f[j];}}f[i]+=maxv;}int maxv=0;for(int i=1;i<=n;i++){maxv=max(maxv,f[i]);}cout<<maxv<<endl;return 0;
}

3.贴邮票问题

P2725 [USACO3.1] 邮票 Stamps - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

//P2725 [USACO3.1] 邮票 Stamps
//https://www.luogu.com.cn/problem/P2725
//63 points
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[55];
int num[10005];
int main(){cin>>k>>n;int maxv=0;for(int i=1;i<=n;i++){cin>>a[i];num[a[i]]=1;maxv=max(maxv,a[i]);}int big=maxv;for(int i=2;i<=k;i++){for(int j=big;j>=1;j--){if(num[j]==1){for(int k=1;k<=n;k++){num[j+a[k]]=1;}}}big=i*maxv;}int i=1;while(num[i]==1) i++;cout<<i-1<<endl;return 0;
}

这篇关于【必看】DP经典类型题详解-考前刷分技巧的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---