10.20贪心+DP专题解题报告

今天终于考了一波水题

高兴坏了

题目:problem

声明:今天有8道题 貌似会比较长XD

1.分苹果

首先所有苹果都是要吃的

但是第一天和第二天吃得到的开心值不同

先假设所有苹果都第二天吃

那么有m个苹果要变成第一天吃

开心值的变化为-y[i]+x[i]

所以可以求出每个苹果的开心值变化量 进行排序 然后挨个取

代码:

// <apple.cpp> – 10/20/15 08:14:05
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
struct apple{
int z,i;
}app[100001];
int a[100001],x[100001],y[100001];
long long ans;
bool cmp(apple a,apple b){
return a.z<b.z;
}
int main(){
freopen(“apple.in”,”r”,stdin);
freopen(“apple.out”,”w”,stdout);
int n=getint();
lol m;
cin>>m;
for(int i=0;i<n;i++)a[i]=getint(),x[i]=getint(),y[i]=getint();
for(int i=0;i<n;i++)app[i].i=i,app[i].z=y[i]-x[i];
sort(app,app+n,cmp);
for(int i=0;i<n;i++){
int now=app[i].i;
if(m>=a[now]){m-=(long long)a[now];ans+=(long long)a[now]*(long long)x[now];}
else{
ans+=(long long)m*(long long)x[now];
a[now]-=m;m=0;
ans+=(long long)a[now]*(long long)y[now];
}
}
cout<<ans;
return 0;
}

2.MOS

每送走最慢的两个人有两种方案

1.用最快的分别送最快的两个过去再回来

用时t[n]+t[0]+t[n-1]+t[0]

2.最快的两个过去,回来第二快的,最慢的两个过去,回来最快的

用时t[1]+t[1]+t[n]+t[0]

由于不能判断2*t[1]和t[0]+t[n-1]的大小关系

于是要取min

在3个人时直接t[0]+t[1]+t[2],2个人时t[1],1个人时t[0]

代码:

// <MOS.cpp> – 10/20/15 08:14:05
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int t[100001];
lol ans;
int main(){
freopen(“MOS.in”,”r”,stdin);
freopen(“MOS.out”,”w”,stdout);
int n=getint();
for(int i=0;i<n;i++)t[i]=getint();
while(1){
if(n==3){ans+=t[0]+t[1]+t[2];break;}
if(n==2){ans+=t[1];break;}
if(n==1){ans+=t[0];break;}
ans+=min(t[0]+t[1]+t[1]+t[n-1],t[0]+t[0]+t[n-2]+t[n-1]);
n-=2;
}
cout<<ans;
return 0;
}

4.立方体大作战

首先可以发现

把每两个相同的数之间看成一个区间

首先只有互相包含的区间才会互相影响

因为如果在内层消除之前消除外层 所需次数会变多

又因为 只有大的区间才能包含小的

所以省点事 直接把区间从小到大排序 然后依次消除

为了快速求出一段区间内有多少格还没被消除

用一个树状数组维护

代码:

// <tet.cpp> – 10/20/15 08:14:05
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define lowbit(x) (x&-x)
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[100001],n,nn;
int b[50001][2];
long long ans;
long long c[100001];
struct ccc{
int l,i;
}cc[50001];
bool cmp(ccc a,ccc b){
return a.l<b.l;
}
void fix(int w,int x){
while(w<=nn){
c[w]+=x;
w+=lowbit(w);
}
}
long long src(int x){
long long sum=0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
freopen(“tet.in”,”r”,stdin);
freopen(“tet.out”,”w”,stdout);
n=getint();nn=2*n;
for(int i=0;i<2*n;i++){
a[i]=getint()-1;
b[a[i]][0]=i;
if(b[a[i]][0]>b[a[i]][1])swap(b[a[i]][0],b[a[i]][1]);
}
for(int i=0;i<n;i++){
cc[i].l=b[i][1]-b[i][0];
cc[i].i=i;
}
sort(cc,cc+n,cmp);
for(int i=1;i<=nn;i++)
for(int o=i-lowbit(i)+1;o<=i;o++)c[i]++;
for(int i=0;i<n;i++){
int now=cc[i].i;
ans+=src(b[now][1])-src(b[now][0]+1);
fix(b[now][0]+1,-1);
fix(b[now][1]+1,-1);
}
cout<<ans;
return 0;
}

5.多人背包

这道题调得我累死了。。

因为每个人的背包都是一样的

所以就相当于装满背包的所有解中价值最大的k个之和

用f[i][j][o]表示前i个数装了j个体积的第o大解

数组f[i][j]即可由f[i-1][j]和f[i-1][j-v[i]]+mny[i]归并排序得到

代码:

// <bags.cpp> – 10/20/15 09:36:39
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int f[201][5001][51],k,V,n,v[201],mny[201],ans;
int main()
{
freopen(“bags.in”,”r”,stdin);
freopen(“bags.out”,”w”,stdout);
cin>>k>>V>>n;
for(int i=1;i<=n;i++)v[i]=getint(),mny[i]=getint();
for(int i=0;i<V;i++)for(int o=0;o<k;o++)f[0][i][o]=-32767;
f[0][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=V;j++){
int a=0,b=0;
for(int o=0;o<k;o++)
if(j<v[i]||f[i-1][j][a]>f[i-1][j-v[i]][b]+mny[i]){
f[i][j][o]=f[i-1][j][a++];
}else f[i][j][o]=f[i-1][j-v[i]][b++]+mny[i];
}
}
for(int o=0;o<k;o++)ans+=f[n][V][o];
cout<<ans<<endl;
return 0;
}

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz