开这个专题主要是为了机试……啊哈哈哈，又菜又爱玩儿系列~就算九月结束应该还是会坚持更新哒，顺带清理了一下之前写得比较乱的博客，乘着夏天还没到来之前修修补补ing
1. 知识点总结
| 题目 | 难度 | 知识点 |
|---|---|---|
| 打包 | 🐸🐸🐸 | 二分（注意二分的内容） |
| 学生节 | 🐸 | DP基础题01背包变式 |
| 和谐宿舍 | 🐸 | 贪心 |
| 最长公共子序列 | 🐸 | DP经典 |
2. 分题题解
2.1 打包
二分基础，卡在了对于时间错误的估计上以至于完全没考虑从重量枚举
【OJ时间估计】
给的提示是二分法，说实话我觉得……昂，直观的想法是每次切最平均的一刀，但是带来的问题是，如果遇到
1,1,1,1,1,1切三刀的情况就明显不对了
直观的解法20/100:
#include<bits/stdc++.h>
using namespace std;
int ans=-1;
int n,m;
vector<int>w;
vector<int>pre_sum;//前缀和
//自定义优先队列
struct Pak{
int l;
int r;
int sum;
bool operator<(const Pak&a){
return sum<a.sum;//大顶堆
}
};
struct cmp{
bool operator ()(Pak a,Pak b){
return a.sum<b.sum;
}
};
priority_queue<Pak,vector<Pak>,cmp>pq;
int getSum(int l,int r){
return pre_sum[r]-pre_sum[l]+w[l];
}
void Div(){
Pak pak=pq.top();
pq.pop();
if(pak.l==pak.r){
pq.push(pak);
return;//切不动最大的，因为不可分割
}else{
//用二分法切割
int low=pak.l;
int high=pak.r;
while(low<high){
int mid=(low+high)/2;
if(getSum(low,mid)<getSum(mid,high)){
low=mid+1;
}else{
high=mid-1;
}
}
//切割后的结果
// printf("%d-%d:%d\n",pak.l,pak.r,pak.sum);
// printf("%d %d\n",low,high);
//重新分配
Pak temp1,temp2;
temp1.l=pak.l;
temp1.r=max(high-1,0);
temp1.sum=getSum(temp1.l,temp1.r) ;
temp2.l=temp1.r+1;
temp2.r=pak.r;
temp2.sum=getSum(temp2.l,temp2.r);
pq.push(temp1);
pq.push(temp2);
}
}
int main(){
scanf("%d%d",&n,&m);
w.resize(n);
pre_sum.resize(n);
for(int i=0;i<n;i++){
scanf("%d",&w[i]);
if(i){
pre_sum[i]=pre_sum[i-1]+w[i];
}else{
pre_sum[i]=w[i];
}
}
//分成m份数，每次在最不均衡的地方划一刀 ，共需要m-1刀
Pak pak;
pak.l=0;pak.r=n-1;pak.sum=getSum(0,n-1);
pq.push(pak);
for(int i=1;i<=m-1;i++){
Div();
}
pak=pq.top();
printf("%d",pak.sum);
return 0;
} 参考了网上的解法，说实话我应该想不出来，因为check的时间复杂度感觉蛮大的，但是可能二分之后效率提升很大叭，它的二分是对于最大包裹重量的枚举的二分，理解起来还是很容易的……
#include<bits/stdc++.h>
using namespace std;
int ans=-1;
int n,m;
vector<int>w;
int low=0,high=0;
bool check(int mid){
int cnt=1;
int sum=w[1];
for(int i=2;i<=n;i++){
if(sum+w[i]<=mid){
sum+=w[i];
}else{
cnt++;
sum=w[i];
}
}
if(cnt<=m)return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
w.resize(n+1);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
low=max(low,w[i]);
high+=w[i];
}
while(low<=high){
int mid=(low+high)/2;
if(check(mid)){
ans=mid;
high=mid-1;
}else{
low=mid+1;
}
}
printf("%d",ans);
return 0;
} 2.2 学生节
有一说一，真的不难……但是DP推导公式怎么说呢，错了就是错了,只能说不要仅仅满足于过样例
#include<bits/stdc++.h>
using namespace std;
int n,T,m;
vector<int>w;
int t;
int dp[1009][1009]={0};//截止到i个题目为止，看了j个节目
int main(){
scanf("%d%d%d",&n,&m,&T);
w.resize(n+1);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=max(dp[i-1][j-1]+w[i],dp[i-1][j]);
}
}
for(int i=0;i<T;i++){
scanf("%d",&t);
printf("%d\n",dp[t][m]);
}
return 0;
}2.3 和谐宿舍
有了第一题的经验之后，感觉思路差不多，都是二分枚举有可能的最小的木板的可能
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<ll>h;
ll ans;
ll low=0;
ll high=0;
bool check(ll size){
//printf("max=%lld\n",size);
//size=最大面积
int cnt=1;
ll sum=h[0];
ll ws=1;
ll hs=h[0];
for(int i=1;i<n;i++){
//更新面积
if(max(hs,h[i])*(ws+1)>size){
cnt++;
hs=h[i];
ws=1;
sum=hs*ws;
}else{
ws++;
hs=max(hs,h[i]);
sum=hs*ws;
}
}
//printf("cnt=%d\n",cnt);
if(cnt<=m){
ans=size;
return true;
}else{
return false;
}
}
int main(){
scanf("%d%d",&n,&m);
h.resize(n);
for(int i=0;i<n;i++){
scanf("%lld",&h[i]);
low=max(low,h[i]);
high+=h[i];
}
//枚举最大的木板
while(low<=high){
ll mid=(low+high)/2;
if(check(mid)){
high=mid-1;
}else{
low=mid+1;
}
}
printf("%lld",ans);
return 0;
} 2.4 最长公共子序列
dp经典题目了，不会的话要好好反思🤣
#include<bits/stdc++.h>
using namespace std;
//输出最长公共子序列
string a;
string b;
int dp[1001][1001]={0};
int ans=0;
int main(){
cin>>a>>b;
int lena=a.size();
int lenb=b.size();
for(int i=0;i<a.length();i++){
for(int j=0;j<b.length();j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
ans=max(ans,dp[i][j]);
}
}
printf("%d",ans);
return 0;
}
