比赛链接
https://ac.nowcoder.com/acm/contest/1102
题解链接
https://ac.nowcoder.com/discuss/333380?type=101&order=0&pos=6&page=2
货物收集
先dfs处理出到达每个点的最小武力值，二分答案后Check一下即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e6+5;
const int INF=0x3f3f3f3f;
struct node{
int from,to;
ll w;
}edge[maxn<<1];
int head[maxn],tot=1;
void add(int from,int to,ll w){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].w=w;
}
int n,v[maxn],weight[maxn];
ll W;
void dfs(int x,int fa){
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to,w=edge[i].w;
if(y==fa) continue;
weight[y]=max(weight[x],w);
dfs(y,x);
}
}
bool check(int mid){
ll res=0;
for(int i=2;i<=n;i++) if(weight[i]<=mid) res+=(ll)v[i];
return res>=W;
}
void solve(){
int l=0,r=INF;
while(l<r){
int mid=l+r>>1;
if(check(mid)==false) l=mid+1;
else r=mid;
}
printf("%d",l);
}
int main() {
// ios::sync_with_stdio(false);
//freopen("货物收集.in","r",stdin);
scanf("%d%lld",&n,&W);
for(int i=2;i<=n;i++) scanf("%d",&v[i]);
int from,to;
ll w;
for(int i=1;i<=n-1;i++){
scanf("%d%d%lld",&from,&to,&w);
add(from,to,w),add(to,from,w);
}
dfs(1,-1);
// for(int i=1;i<=n;i++) printf("%d ",weight[i]);
// printf("\n");
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
货物分组
DP方程疯狂优化即可。具体详见代码注释。
代码如下（method_1为60pts，method_2为100pts）
/*
*/
#define method_2
#ifdef method_1
/*
利用“费用提前计算”，优化DP，复杂度n^2
60pts
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int maxlog=15;
const int INF=0x3f3f3f3f;
int n,t;
ll W,a[maxn],sum[maxn],cost[maxn][maxn],d[maxn],mx[maxn][maxlog],mn[maxn][maxlog];
void prest(){
for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];
for(int j=1;j<t;j++) for(int i=1;i<=n-(1<<j)+1;i++){
mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
}
}
ll getmx(int l,int r){
int k=log(r-l+1)/log(2);
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
ll getmn(int l,int r){
int k=log(r-l+1)/log(2);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
void pre(){
for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){
cost[i][j]=sum[j]-sum[i-1]+getmx(i,j)-getmn(i,j);
// D(i);D(j);D(cost[i][j]);E;
}
}
void dp(){
memset(d,INF,sizeof(d));
d[0]=0;
for(int i=1;i<=n;i++) for(int j=0;j<=i-1;j++){
if(sum[i]-sum[j]>W) continue;
d[i]=min(d[i],d[j]+cost[j+1][i]+sum[n]-sum[i]);
//本来是对j+1~n的任务产生影响，但是这里由于j+1~i的费用已经包括在cost[j+1,i]中了，所以这里是sum[n]-sum[i]而不是sum[n]-sum[j]
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("货物分组.in","r",stdin);
scanf("%d%lld",&n,&W);
t=log(n)/log(2)+1;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
prest();
pre();
dp();
printf("%lld",d[n]);
return 0;
}
#endif
#ifdef method_2
/*
优化上述的DP方程。
d[i]=min{d[j]+mx(i,j)-mn(i,j)-sum[j]}+sum[n]
因此，用一个单调栈维护min{f[j]+mx(i,j)-mn(i,j)-sum[j]}。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int maxlog=22;
const int INF=0x3f3f3f3f;
int n,t;
ll W,a[maxn],sum[maxn],d[maxn],mx[maxn][maxlog],mn[maxn][maxlog];
void prest(){
for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];
for(int j=1;j<t;j++) for(int i=1;i<=n-(1<<j)+1;i++){
mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
}
}
ll getmx(int l,int r){
int k=log(r-l+1)/log(2);
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
ll getmn(int l,int r){
int k=log(r-l+1)/log(2);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int q[maxn],head,tail;
void dp(){
memset(d,INF,sizeof(d));
d[0]=0;
head=tail=1;
q[head]=0;
for(int i=1;i<=n;i++){
while(head<=tail&&sum[i]-sum[q[head]]>W) head++;
for(int j=head;j<=tail;j++){
d[i]=min(d[i],d[q[j]]+getmx(q[j]+1,i)-getmn(q[j]+1,i)-sum[q[j]]+sum[n]);
}
while(head<=tail&&d[q[tail]]-sum[q[tail]]>=d[i]-sum[i]) tail--;
q[++tail]=i;
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("货物分组.in","r",stdin);
scanf("%d%lld",&n,&W);
t=log(n)/log(2)+1;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
prest();
dp();
printf("%lld",d[n]);
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
网友评论